Task: | Backup |
Sender: | ollpu |
Submission time: | 2019-03-07 15:12:36 +0200 |
Language: | C++ |
Status: | READY |
Result: | 100 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 30 |
#2 | ACCEPTED | 30 |
#3 | ACCEPTED | 40 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.02 s | 1, 2, 3 | details |
#2 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#3 | ACCEPTED | 0.25 s | 3 | details |
#4 | ACCEPTED | 0.23 s | 3 | details |
#5 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#6 | ACCEPTED | 0.03 s | 2, 3 | details |
#7 | ACCEPTED | 0.03 s | 1, 2, 3 | details |
#8 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#9 | ACCEPTED | 0.02 s | 2, 3 | details |
#10 | ACCEPTED | 0.03 s | 2, 3 | details |
#11 | ACCEPTED | 0.07 s | 3 | details |
#12 | ACCEPTED | 0.25 s | 3 | details |
#13 | ACCEPTED | 0.13 s | 3 | details |
#14 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#15 | ACCEPTED | 0.01 s | 2, 3 | details |
#16 | ACCEPTED | 0.04 s | 3 | details |
#17 | ACCEPTED | 0.25 s | 3 | details |
#18 | ACCEPTED | 0.02 s | 2, 3 | details |
#19 | ACCEPTED | 0.01 s | 2, 3 | details |
#20 | ACCEPTED | 0.16 s | 3 | details |
Code
#include <bits/stdc++.h>using namespace std;#define F first#define S secondset<pair<long, int>> ch;long pfi[101010];set<int> xh;inline void erase_idx(int i) {long val = pfi[i];xh.erase(i);ch.erase({val, i});}int main() {ios::sync_with_stdio(0);cin.tie(0);int n, k;cin >> n >> k;int lv = -1;for (int i = 0; i < n; ++i) {int nv;cin >> nv;if (i) {ch.insert({nv-lv, i});xh.insert(i);pfi[i] = nv-lv;}lv = nv;}long res = 0;for (int kr = 0; kr < k; ++kr) {auto it = ch.begin();auto p = *it;auto iat = xh.upper_bound(p.S);auto ibt = prev(iat);res += p.F;if (ibt == xh.begin()) {erase_idx(p.S);if (iat != xh.end()) erase_idx(*iat);} else {ibt--;if (iat == xh.end()) {erase_idx(*ibt);erase_idx(p.S);} else {pfi[p.S] = pfi[*iat] + pfi[*ibt] - p.F;ch.erase(it);ch.insert({pfi[p.S], p.S});erase_idx(*ibt);erase_idx(*iat);}}}cout << res << endl;}
Test details
Test 1
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
2 1 0 1000000000 |
correct output |
---|
1000000000 |
user output |
---|
1000000000 |
Test 2
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
17 8 101266 101394 101458 101490 ... |
correct output |
---|
340 |
user output |
---|
340 |
Test 3
Group: 3
Verdict: ACCEPTED
input |
---|
100000 49000 29983 53806 76909 106815 ... |
correct output |
---|
411321413 |
user output |
---|
411321413 |
Test 4
Group: 3
Verdict: ACCEPTED
input |
---|
100000 30000 29983 53806 76909 106815 ... |
correct output |
---|
100755932 |
user output |
---|
100755932 |
Test 5
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
20 10 126229031 250138471 333910089 443521720 ... |
correct output |
---|
537092323 |
user output |
---|
537092323 |
Test 6
Group: 2, 3
Verdict: ACCEPTED
input |
---|
10000 4999 168328 266967 462469 639689 ... |
correct output |
---|
492516409 |
user output |
---|
492516409 |
Test 7
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
10 4 165 375 439 456 ... |
correct output |
---|
44 |
user output |
---|
44 |
Test 8
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
20 9 4336 4500 4552 4702 ... |
correct output |
---|
773 |
user output |
---|
773 |
Test 9
Group: 2, 3
Verdict: ACCEPTED
input |
---|
2001 1000 1230 1440 1630 2230 ... |
correct output |
---|
493503 |
user output |
---|
493503 |
Test 10
Group: 2, 3
Verdict: ACCEPTED
input |
---|
10000 3000 245408 417449 650973 863296 ... |
correct output |
---|
101056127 |
user output |
---|
101056127 |
Test 11
Group: 3
Verdict: ACCEPTED
input |
---|
50000 20000 37035 37042 37046 37052 ... |
correct output |
---|
129968 |
user output |
---|
129968 |
Test 12
Group: 3
Verdict: ACCEPTED
input |
---|
99999 48000 15929 43928 65765 86730 ... |
correct output |
---|
375524431 |
user output |
---|
375524431 |
Test 13
Group: 3
Verdict: ACCEPTED
input |
---|
100000 1000 536 9214 34619 53734 ... |
correct output |
---|
75975 |
user output |
---|
75975 |
Test 14
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
10 4 5851 5854 5856 5859 ... |
correct output |
---|
2664 |
user output |
---|
2664 |
Test 15
Group: 2, 3
Verdict: ACCEPTED
input |
---|
100 45 3712 13742 17394 19428 ... |
correct output |
---|
140256 |
user output |
---|
140256 |
Test 16
Group: 3
Verdict: ACCEPTED
input |
---|
20000 400 3174 3175 3176 3179 ... |
correct output |
---|
803105 |
user output |
---|
803105 |
Test 17
Group: 3
Verdict: ACCEPTED
input |
---|
100000 49000 3605 14510 18001 20881 ... |
correct output |
---|
162316123 |
user output |
---|
162316123 |
Test 18
Group: 2, 3
Verdict: ACCEPTED
input |
---|
100 50 0 1000000 1000002 1000005 ... |
correct output |
---|
1002499 |
user output |
---|
1002499 |
Test 19
Group: 2, 3
Verdict: ACCEPTED
input |
---|
1000 500 0 1000000 1000002 1000005 ... |
correct output |
---|
1249999 |
user output |
---|
1249999 |
Test 20
Group: 3
Verdict: ACCEPTED
input |
---|
100000 49494 123 65659 98427 114811 ... |
correct output |
---|
250954854 |
user output |
---|
250954854 |