#include "bits/stdc++.h"
using namespace std;
#define int int64_t
#define pb push_back
using pii=pair<int,int>;
const int lim=2e5+100;
int mod=1e9+7;
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#ifdef Local
freopen(".in","r",stdin);freopen(".out","w",stdout);
#endif
int n;
cin>>n;
int a[n],b[n],ll[n]{},rr[n]{};
for(int i=0;i<n;i++){cin>>a[i];b[i]=a[i];}
priority_queue<pii>pq;
for(int i=0;i<n;i++){
pq.push({a[i],i});
}
int cnt=0;
int pref[n];
pref[0]=a[0];
if(n)pref[1]=a[1];
for(int i=2;i<n;i++){
pref[i]=pref[i-2]+a[i];
}
auto f=[&](int l,int r){
return pref[r]-(1<l?pref[l-2]:int(0));
};
set<pii>st;
int ans=0;
for(int i=1;i<=(n+1)/2;i++){
while(pq.size()){
auto[val,ind]=pq.top();
pq.pop();
if(val!=b[ind])continue;
auto p=st.lower_bound({ind,ind}),q=(p==st.begin())?st.end():prev(p);
int l=ind,r=ind;
if(q!=st.end()){
if(q->first<=ind&&ind<=q->second)continue;
}
//cerr<<val<<" "<<ind<<"\n";
if(p!=st.end()&&p->first<=ind+2){
r=p->second;
st.erase(p);
}
if(q!=st.end()&&ind-2<=q->second){
l=q->first;
st.erase(q);
}
if((r&1)!=(ind&1)){
r++;
if(n<=r)r-=2;
}
if((l&1)!=(ind&1)){
l--;
if(l<0)l-=2;
}
ans+=val;
//cerr<<l<<" "<<r<<" lr\n";
st.insert({l,r});
if(l){
int k=f(l,r)-((l+1<n)?f(l+1,r+1<n?r+1:r-1):0);
ll[l-1]=k;
b[l-1]=a[l-1]-ll[l-1]-rr[l-1];
pq.push({b[l-1],l-1});
}
if(r+1<n){
int k=f(l,r)-((0<=r-1)?f(0<=l-1?l-1:l+1,r-1):0);
rr[r+1]=k;
b[r+1]=a[r+1]-ll[r+1]-rr[r+1];
pq.push({b[r+1],r+1});
}
break;
}
cout<<ans<<"\n";
/*
for(int i:b){
cerr<<i<<" ";
}cerr<<"\n";
cerr<<"ranges:\n";
for(auto[f,s]:st){
cerr<<f<<" "<<s<<"\n";
}cerr<<"\n";
*/
}
}
Compilation message
candies.cpp: In function 'int main()':
candies.cpp:25:9: warning: unused variable 'cnt' [-Wunused-variable]
25 | int cnt=0;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
