#include <bits/stdc++.h>
using namespace std;
typedef pair<long long, long long> ii;
set<ii> best;
set<long long> idx;
int main(){
int n;
cin >> n;
long long arr[n];
for(int i = 0;i < n;i++){
cin >> arr[i];
best.insert(ii(arr[i],i));
idx.insert(i);
}
idx.insert(-1);
idx.insert(n+1);
long long ans = 0;
for(int k = 1;k <= (n+1)/2;k++){
set<ii>::iterator it = (--best.end());
best.erase(it);
idx.erase(it->second);
ans += it->first;
int s = it->second;
long long r = *idx.upper_bound(s);
long long l = *(--idx.lower_bound(s));
arr[s] *= -1;
if(l >= 0){
arr[s] += arr[l];
best.erase(ii(arr[l],l));
idx.erase(l);
}
if(r <= n-1){
arr[s] += arr[r];
best.erase(ii(arr[r],r));
idx.erase(r);
}
if(r <= n-1 && l >= 0){
best.insert(ii(arr[s],s));
idx.insert(s);
}
cout << ans << "\n";
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
6 ms |
760 KB |
Output is correct |
| 2 |
Correct |
6 ms |
632 KB |
Output is correct |
| 3 |
Correct |
6 ms |
632 KB |
Output is correct |
| 4 |
Correct |
6 ms |
632 KB |
Output is correct |
| 5 |
Correct |
6 ms |
632 KB |
Output is correct |
| 6 |
Correct |
6 ms |
632 KB |
Output is correct |
| 7 |
Correct |
6 ms |
632 KB |
Output is correct |
| 8 |
Correct |
5 ms |
632 KB |
Output is correct |
| 9 |
Correct |
5 ms |
632 KB |
Output is correct |
| 10 |
Correct |
5 ms |
632 KB |
Output is correct |
| 11 |
Correct |
7 ms |
632 KB |
Output is correct |
| 12 |
Correct |
6 ms |
604 KB |
Output is correct |
| 13 |
Correct |
6 ms |
632 KB |
Output is correct |
| 14 |
Correct |
6 ms |
632 KB |
Output is correct |
| 15 |
Correct |
6 ms |
632 KB |
Output is correct |
| 16 |
Correct |
6 ms |
632 KB |
Output is correct |
| 17 |
Correct |
6 ms |
632 KB |
Output is correct |
| 18 |
Correct |
6 ms |
632 KB |
Output is correct |
| 19 |
Correct |
5 ms |
632 KB |
Output is correct |
| 20 |
Correct |
5 ms |
632 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
6 ms |
760 KB |
Output is correct |
| 2 |
Correct |
6 ms |
632 KB |
Output is correct |
| 3 |
Correct |
6 ms |
632 KB |
Output is correct |
| 4 |
Correct |
6 ms |
632 KB |
Output is correct |
| 5 |
Correct |
6 ms |
632 KB |
Output is correct |
| 6 |
Correct |
6 ms |
632 KB |
Output is correct |
| 7 |
Correct |
6 ms |
632 KB |
Output is correct |
| 8 |
Correct |
5 ms |
632 KB |
Output is correct |
| 9 |
Correct |
5 ms |
632 KB |
Output is correct |
| 10 |
Correct |
5 ms |
632 KB |
Output is correct |
| 11 |
Correct |
7 ms |
632 KB |
Output is correct |
| 12 |
Correct |
6 ms |
604 KB |
Output is correct |
| 13 |
Correct |
6 ms |
632 KB |
Output is correct |
| 14 |
Correct |
6 ms |
632 KB |
Output is correct |
| 15 |
Correct |
6 ms |
632 KB |
Output is correct |
| 16 |
Correct |
6 ms |
632 KB |
Output is correct |
| 17 |
Correct |
6 ms |
632 KB |
Output is correct |
| 18 |
Correct |
6 ms |
632 KB |
Output is correct |
| 19 |
Correct |
5 ms |
632 KB |
Output is correct |
| 20 |
Correct |
5 ms |
632 KB |
Output is correct |
| 21 |
Correct |
892 ms |
27320 KB |
Output is correct |
| 22 |
Correct |
902 ms |
27328 KB |
Output is correct |
| 23 |
Correct |
852 ms |
27296 KB |
Output is correct |
| 24 |
Correct |
490 ms |
27256 KB |
Output is correct |
| 25 |
Correct |
468 ms |
27288 KB |
Output is correct |
| 26 |
Correct |
455 ms |
27116 KB |
Output is correct |
| 27 |
Correct |
476 ms |
27292 KB |
Output is correct |
| 28 |
Correct |
479 ms |
27328 KB |
Output is correct |
| 29 |
Correct |
478 ms |
27384 KB |
Output is correct |
| 30 |
Correct |
514 ms |
27248 KB |
Output is correct |
| 31 |
Correct |
502 ms |
27512 KB |
Output is correct |
| 32 |
Correct |
496 ms |
27504 KB |
Output is correct |
| 33 |
Correct |
681 ms |
27128 KB |
Output is correct |
| 34 |
Correct |
648 ms |
27144 KB |
Output is correct |
| 35 |
Correct |
653 ms |
27236 KB |
Output is correct |
| 36 |
Correct |
908 ms |
27384 KB |
Output is correct |
| 37 |
Correct |
966 ms |
27316 KB |
Output is correct |
| 38 |
Correct |
943 ms |
27436 KB |
Output is correct |
| 39 |
Correct |
471 ms |
27280 KB |
Output is correct |
| 40 |
Correct |
467 ms |
27128 KB |
Output is correct |
| 41 |
Correct |
462 ms |
27240 KB |
Output is correct |
| 42 |
Correct |
477 ms |
27264 KB |
Output is correct |
| 43 |
Correct |
478 ms |
27396 KB |
Output is correct |
| 44 |
Correct |
478 ms |
27400 KB |
Output is correct |
| 45 |
Correct |
521 ms |
27360 KB |
Output is correct |
| 46 |
Correct |
493 ms |
27256 KB |
Output is correct |
| 47 |
Correct |
494 ms |
27360 KB |
Output is correct |
| 48 |
Correct |
652 ms |
27100 KB |
Output is correct |
| 49 |
Correct |
665 ms |
27140 KB |
Output is correct |
| 50 |
Correct |
648 ms |
27256 KB |
Output is correct |
