#include <bits/stdc++.h>
using namespace std;
long long a[200005];
set <pair <long long, long long>> choices;
long long l[200005], r[200005];
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
long long n; cin >> n;
for (long long i = 1; i <= n; i++){
cin >> a[i]; l[i] = i - 1; r[i] = i + 1;
choices.insert(make_pair(-a[i], i));
}
long long ans = 0;
for (long long c = 0; c < (n + 1) / 2; c++){
pair <long long, long long> mx = *choices.begin();
choices.erase(choices.begin());
ans -= mx.first;
long long id = mx.second, lf = l[id], rg = r[id];
if (lf) choices.erase(make_pair(-a[lf], lf));
if (rg <= n) choices.erase(make_pair(-a[rg], rg));
if (lf) l[id] = l[lf];
else l[id] = 0;
if (rg <= n) r[id] = r[rg];
else r[id] = n + 1;
if (l[id]) r[l[id]] = id;
if (r[id] <= n) l[r[id]] = id;
a[id] = a[lf] + a[rg] - a[id];
choices.insert(make_pair(-a[id], id));
cout << ans << "\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
