#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5+1;
const ll INF = 1e17;
int n;
ll a[N], pre[N], nxt[N];
priority_queue<pair<ll, int> > pq;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> a[i];
if(i > 1) pre[i] = i-1;
if(i < n) nxt[i] = i+1;
pq.emplace(a[i], i);
}
ll ans = 0;
for(int z = 1; z <= n+1 >> 1; z++) {
while(pq.top().first != a[pq.top().second]) pq.pop();
int i = pq.top().second;
ans += a[i];
cout << ans << '\n';
int l = pre[i], r = nxt[i];
nxt[i] = nxt[r];
pre[i] = pre[l];
pre[nxt[r]] = i;
nxt[pre[l]] = i;
if(l && r) a[i] = max(a[l] + a[r] - a[i], -INF);
a[l] = a[r] = -INF;
pq.emplace(a[i], i);
}
}
Compilation message
candies.cpp: In function 'int main()':
candies.cpp:22:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
for(int z = 1; z <= n+1 >> 1; z++) {
~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
