#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;
pre[0]=-1,nex[0]=1;
pre[n+1]=n,nex[n+1]=n+2;
for (int i=1; i<=n; i++) {
cin>>a[i];
st.insert({a[i],i});
pre[i]=i-1,nex[i]=i+1;
}
a[0]=a[n+1]=-1e15;
for (int i=1; i<=(n+1)/2; i++) {
it=st.end(); --it;
y=(*it).second;
pr=pre[y],nx=nex[y];
st.erase({a[y],y});
ans+=a[y],a[y]=-a[y];
if (pr!=-1) {
a[y]+=a[pr];
nex[pre[pr]]=y,pre[y]=pre[pr];
st.erase({a[pr],pr});
}
if (nx!=n+2) {
a[y]+=a[nx];
nex[y]=nex[nx],pre[nex[nx]]=y;
st.erase({a[nx],nx});
}
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 |
Correct |
7 ms |
512 KB |
Output is correct |
| 2 |
Correct |
7 ms |
512 KB |
Output is correct |
| 3 |
Correct |
7 ms |
512 KB |
Output is correct |
| 4 |
Correct |
7 ms |
512 KB |
Output is correct |
| 5 |
Correct |
7 ms |
640 KB |
Output is correct |
| 6 |
Correct |
7 ms |
512 KB |
Output is correct |
| 7 |
Correct |
7 ms |
512 KB |
Output is correct |
| 8 |
Correct |
7 ms |
512 KB |
Output is correct |
| 9 |
Correct |
7 ms |
512 KB |
Output is correct |
| 10 |
Correct |
7 ms |
384 KB |
Output is correct |
| 11 |
Correct |
7 ms |
512 KB |
Output is correct |
| 12 |
Correct |
7 ms |
512 KB |
Output is correct |
| 13 |
Correct |
7 ms |
512 KB |
Output is correct |
| 14 |
Correct |
7 ms |
512 KB |
Output is correct |
| 15 |
Correct |
7 ms |
512 KB |
Output is correct |
| 16 |
Correct |
7 ms |
512 KB |
Output is correct |
| 17 |
Correct |
7 ms |
512 KB |
Output is correct |
| 18 |
Correct |
7 ms |
512 KB |
Output is correct |
| 19 |
Correct |
7 ms |
512 KB |
Output is correct |
| 20 |
Correct |
7 ms |
512 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
512 KB |
Output is correct |
| 2 |
Correct |
7 ms |
512 KB |
Output is correct |
| 3 |
Correct |
7 ms |
512 KB |
Output is correct |
| 4 |
Correct |
7 ms |
512 KB |
Output is correct |
| 5 |
Correct |
7 ms |
640 KB |
Output is correct |
| 6 |
Correct |
7 ms |
512 KB |
Output is correct |
| 7 |
Correct |
7 ms |
512 KB |
Output is correct |
| 8 |
Correct |
7 ms |
512 KB |
Output is correct |
| 9 |
Correct |
7 ms |
512 KB |
Output is correct |
| 10 |
Correct |
7 ms |
384 KB |
Output is correct |
| 11 |
Correct |
7 ms |
512 KB |
Output is correct |
| 12 |
Correct |
7 ms |
512 KB |
Output is correct |
| 13 |
Correct |
7 ms |
512 KB |
Output is correct |
| 14 |
Correct |
7 ms |
512 KB |
Output is correct |
| 15 |
Correct |
7 ms |
512 KB |
Output is correct |
| 16 |
Correct |
7 ms |
512 KB |
Output is correct |
| 17 |
Correct |
7 ms |
512 KB |
Output is correct |
| 18 |
Correct |
7 ms |
512 KB |
Output is correct |
| 19 |
Correct |
7 ms |
512 KB |
Output is correct |
| 20 |
Correct |
7 ms |
512 KB |
Output is correct |
| 21 |
Correct |
439 ms |
19452 KB |
Output is correct |
| 22 |
Correct |
429 ms |
19448 KB |
Output is correct |
| 23 |
Correct |
514 ms |
19448 KB |
Output is correct |
| 24 |
Correct |
241 ms |
19320 KB |
Output is correct |
| 25 |
Correct |
258 ms |
19320 KB |
Output is correct |
| 26 |
Correct |
249 ms |
19320 KB |
Output is correct |
| 27 |
Correct |
276 ms |
19448 KB |
Output is correct |
| 28 |
Correct |
275 ms |
19452 KB |
Output is correct |
| 29 |
Correct |
277 ms |
19448 KB |
Output is correct |
| 30 |
Correct |
294 ms |
19448 KB |
Output is correct |
| 31 |
Correct |
294 ms |
19448 KB |
Output is correct |
| 32 |
Correct |
272 ms |
19448 KB |
Output is correct |
| 33 |
Correct |
370 ms |
19192 KB |
Output is correct |
| 34 |
Correct |
325 ms |
19204 KB |
Output is correct |
| 35 |
Correct |
362 ms |
19320 KB |
Output is correct |
| 36 |
Correct |
498 ms |
19448 KB |
Output is correct |
| 37 |
Correct |
427 ms |
19460 KB |
Output is correct |
| 38 |
Correct |
499 ms |
19448 KB |
Output is correct |
| 39 |
Correct |
252 ms |
19332 KB |
Output is correct |
| 40 |
Correct |
241 ms |
19320 KB |
Output is correct |
| 41 |
Correct |
257 ms |
19320 KB |
Output is correct |
| 42 |
Correct |
274 ms |
19448 KB |
Output is correct |
| 43 |
Correct |
277 ms |
19448 KB |
Output is correct |
| 44 |
Correct |
267 ms |
19448 KB |
Output is correct |
| 45 |
Correct |
277 ms |
19448 KB |
Output is correct |
| 46 |
Correct |
297 ms |
19448 KB |
Output is correct |
| 47 |
Correct |
272 ms |
19448 KB |
Output is correct |
| 48 |
Correct |
361 ms |
19192 KB |
Output is correct |
| 49 |
Correct |
329 ms |
19320 KB |
Output is correct |
| 50 |
Correct |
320 ms |
19192 KB |
Output is correct |
