Task: | Backup |
Sender: | jarvenp |
Submission time: | 2019-03-07 18:03:17 +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.03 s | 1, 2, 3 | details |
#3 | ACCEPTED | 0.32 s | 3 | details |
#4 | ACCEPTED | 0.27 s | 3 | details |
#5 | ACCEPTED | 0.03 s | 1, 2, 3 | details |
#6 | ACCEPTED | 0.04 s | 2, 3 | details |
#7 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#8 | ACCEPTED | 0.02 s | 1, 2, 3 | details |
#9 | ACCEPTED | 0.02 s | 2, 3 | details |
#10 | ACCEPTED | 0.04 s | 2, 3 | details |
#11 | ACCEPTED | 0.10 s | 3 | details |
#12 | ACCEPTED | 0.32 s | 3 | details |
#13 | ACCEPTED | 0.19 s | 3 | details |
#14 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#15 | ACCEPTED | 0.02 s | 2, 3 | details |
#16 | ACCEPTED | 0.05 s | 3 | details |
#17 | ACCEPTED | 0.32 s | 3 | details |
#18 | ACCEPTED | 0.02 s | 2, 3 | details |
#19 | ACCEPTED | 0.02 s | 2, 3 | details |
#20 | ACCEPTED | 0.32 s | 3 | details |
Compiler report
input/code.cpp: In function 'int main()': input/code.cpp:46:15: warning: unused variable 'temp' [-Wunused-variable] int64_t temp = (*it).F; ^~~~ input/code.cpp:54:15: warning: unused variable 'temp' [-Wunused-variable] int64_t temp = (*it2).F; ^~~~ input/code.cpp:55:15: warning: unused variable 'temp2' [-Wunused-variable] int64_t temp2 = (*it2).S; ^~~~~
Code
#include <bits/stdc++.h>using namespace std;#define F first#define S secondint64_t n,k;int64_t d[100000];multiset<pair<int64_t,int64_t>> ds;set<pair<int64_t,int64_t>> vals;int64_t dd[100000];int main(){cin >> n >> k;for(int64_t i=0; i<n; i++){cin >> d[i];vals.insert({d[i],i});if(i > 0){ds.insert({d[i]-d[i-1],i});dd[i] = d[i]-d[i-1];}}int64_t ans = 0;for(int64_t i=0; i<k; i++){pair<int64_t,int64_t> p = *ds.begin();ds.erase(p);set<pair<int64_t,int64_t>>::iterator it;/* if((d[p.S]-d[p.S-1]) != p.F){int64_t i2;for(i2=p.S-1; (d[p.S]-d[i2]) != p.F; i2 -= 2){ans += (d[i2+1]-d[i2]);ans -= (d[i2]-d[i2-1]);}ans += (d[i2+1]-d[i2]);it = vals.find({d[i2],i2});}else{it = vals.find({d[p.S-1],p.S-1});ans += p.F;}*/ans += p.F;auto it2 = vals.find({d[p.S],p.S});it = it2;it--;if(it != vals.begin()){int64_t temp = (*it).F;int64_t temp2 = (*it).S;it--;ds.erase({dd[temp2],temp2});it++;}if(it2 != --vals.end()){int64_t temp = (*it2).F;int64_t temp2 = (*it2).S;it2++;ds.erase({dd[(*it2).S],(*it2).S});it2--;}if((it != vals.begin()) && (it2 != --vals.end())){it--;it2++;int64_t dis = 0;for(int64_t i3 = (*it).S; i3 < (*it2).S; i3 += 2){dis += (d[i3+1]-d[i3]);if((i3+1) !=(*it2).S){dis -= (d[i3+2]-d[i3+1]);}}dd[(*it2).S] = dis;// cout << dis << "\n";ds.insert({dis,(*it2).S});it++;it2--;}vals.erase(it);vals.erase(it2);/* for(auto it3 = ds.begin(); it3 != ds.end(); it3++){cout << (*it3).F << " ";}cout << "\n";for(auto it3 = vals.begin(); it3 !=vals.end(); it3++){cout << (*it3).F << " ";}cout << "\n";*///cout << ans << "\n";}cout << ans << "\n";}
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 |