#include <bits/stdc++.h>
using namespace std;
#define dbgv(v) cout<<#v<<" = "; f(i,0,v.size()) cout<<v[i]<<" "; cout<<endl
#define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl
#define erorp(x) cout<<#x<<"={"<<(x.F)<<" , "<<x.S<<"}"<<endl
#define eror(x) cout<<#x<<'='<<(x)<<endl
#define f_(i,a,b) for(int i=a;i>=b;i--)
#define f(i,a,b) for(int i=a;i<b;i++)
#define nb(x) __builtin_popcount(x)
#define all(v) v.begin(),v.end()
#define bit(n,k) (((n)>>(k))&1)
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define lst(x) x[x.size()-1]
#define sz(x) int(x.size())
#define mp make_pair
#define ll long long
#define pb push_back
#define S second
#define F first
#define int ll
const int N=1e6+99,S=2;
int n,t,ans,a[N],res[N],ps[N][S],L[N],R[N];
set<pair<int,pair<int,int> > > s;
void Add(int l,int r){
if(r>n || l<1) return ;
int res=(ps[r][1]-ps[l-1][0])-(ps[r][0]-ps[l-1][1]);
s.insert({res,{l,r}});
}
void del(int l,int r){
if(r>n || l<1) return ;
int res=(ps[r][1]-ps[l-1][0])-(ps[r][0]-ps[l-1][1]);
s.erase({res,{l,r}});
}
main(){
cin>>n;
f(i,1,n+1){
L[i]=R[i]=i;
cin>>a[i];
s.insert({a[i],{L[i],R[i]}});
}
f(i,1,n+1){
ps[i][0]=ps[i-1][1];
ps[i][1]=ps[i-1][0]+a[i];
}
f(t,0,(n+1)/2-1){
pair<int,pair<int,int> > p=*s.rbegin();
int l=p.S.F-1,r=p.S.S+1;
R[l+1]=0,L[r-1]=0;
s.erase(p);
ans+=p.F;
if(L[l]){
int copy=l;
del(L[l],l);
l=L[l];
L[copy]=0,R[copy]=0;
R[l]=r;
}
if(R[r]){
int copy=r;
del(r,R[r]);
r=R[r];
L[copy]=0,R[copy]=0;
L[r]=l;
}
Add(l,r);
R[l]=r;
L[r]=l;
cout<<ans<<" ";
}
int sum0=0,sum1=0;
f(i,1,n+1){
if(i&1) sum1+=a[i];
else sum0+=a[i];
}
if(n&1){
cout<<sum1;
}
else{
cout<<max(sum0,sum1);
}
}
/*
5
3 5 1 7 6
7 12 10
20
1 5 7 4 1 6 5 4 7 6 7 8 9 7 4 2 3 2 1 4
9 16 23 30 36 40 44 47 49 48
50
5101 15771 20482 15590 21148 25161 20231 19178 4252 21604 18338 31380 8817 29875 15505 5241 31720 16155 29743 22362 27469 26889 11591 10666 5343 16149 5670 1099 17025 1503 14836 31385 23474 25149 22596 937 6591 3225 23273 26834 19511 21396 24075 32109 16800 12783 32379 986 10344 31660
32379 64488 96208 127868 159253 190633 220508 250251 277720 304554 329715 354864 376468 397864 418346 437524 454549 470698 482289 493168 499759 504131 507451 502315 457630
32379 64488 96208 127868 159253 190633 220508 250251 277720 304554 329715 354864 376468 397864 418346 437524 454549 470698 482289 493168 499759 504131 507451 505477 549710
*/
Compilation message
candies.cpp:39:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
39 | main(){
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
