#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 2e5 + 5;
int N;
ll a[maxn];
struct node {
ll val;
node *l, *r;
node () {
val = 0;
l = r = NULL;
}
};
using llp = pair<ll, node*>;
multiset<llp> Q;
int main(int argc, char const *argv[])
{
// freopen("in", "r", stdin);
cin >> N;
for(int i = 1; i <= N; i++) {
cin >> a[i];
}
node *prev = NULL;
for(int i = 1; i <= N; i++) {
node *now = new node();
now -> val = a[i];
now -> l = prev;
if(prev) now -> l -> r = now;
Q.insert(llp(a[i], now));
prev = now;
}
ll ans = 0;
for(int i = 1; i <= (N - 1) / 2 + 1; i++) {
// take best
node* best = Q.rbegin() -> second;
// update answer
ans += best -> val;
// create virtual elem
node *now = new node();
now -> val = -best -> val;
int flag = 1;
if(best -> l) {
now -> val += best -> l -> val;
now -> l = best -> l -> l;
Q.erase(llp(best -> l -> val, best -> l));
delete(best -> l);
} else {
flag = 0;
}
if(best -> r) {
now -> val += best -> r -> val;
now -> r = best -> r -> r;
Q.erase(llp(best -> r -> val, best -> r));
delete(best -> r);
} else {
flag = 0;
}
if(now -> l) now -> l -> r = now;
if(now -> r) now -> r -> l = now;
Q.erase(--Q.end());
if(flag) {
Q.insert(llp(now -> val, now));
}
cout << ans << endl;
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
