#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+5;
int n,y,nx,pr,pre[N],nex[N];
ll ans,a[N];
set < pair < ll , int > > st;
set < pair < ll , int > > :: iterator it;
main () {
cin>>n;
for (int i=1; i<=n; i++) {
cin>>a[i];
st.insert({a[i],i});
pre[i]=i-1,nex[i]=i+1;
}
for (int i=1; i<=(n+1)/2; i++) {
it=st.end(); --it;
y=(*it).second;
pr=pre[y],nx=nex[y];
st.erase(st.find({a[y],y}));
ans+=a[y],a[y]=-a[y];
if (0!=pr) {
a[y]+=a[pr];
nex[pre[pr]]=y,pre[y]=pre[pr];
st.erase(st.find({a[pr],pr}));
}
if (n+1!=nx) {
a[y]+=a[nx];
nex[y]=nex[nx],pre[nex[nx]]=y;
st.erase(st.find({a[nx],nx}));
}
if (y==n) a[y]-=1e9;
if (y==1) a[y]-=1e9;
st.insert({a[y],y});
cout<<ans<<"\n";
}
}
Compilation message
candies.cpp:9:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main () {
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
