| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 57418 | fefe | Holiday (IOI14_holiday) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define MAX_N 100005
using namespace std;
typedef long long LL;
struct pst{
LL cnt,sum;
pst *l,*r;
pst(LL cnt,LL sum,pst *l,pst *r):cnt(cnt),sum(sum),l(l),r(r){}
pst *update(LL idx,LL p){
if(idx<0) return new pst(cnt+1,sum+p,NULL,NULL);
if(p>>idx&1) return new pst(cnt+1,sum+p,l,r->update(idx-1,p));
return new pst(cnt+1,sum+p,l->update(idx-1,p),r);
}
}*tree[MAX_N];
LL n,st,d,dx,ans;
LL s_t[MAX_N],s_tt[MAX_N],e_t[MAX_N],e_tt[MAX_N];
LL get_sum(LL idx,pst *l,pst *r,LL x,LL p){
if(idx<0) return min(x,r->cnt-l->cnt)*p;
LL y=r->l->cnt-l->l->cnt,z=r->r->cnt-l->r->cnt;
if(r->cnt-l->cnt==p) return r->sum-l->sum;
if(y<x && z!=0) return get_sum(idx-1,l->r,r->r,x-y,p|(1LL<<idx))+r->l->sum-l->l->sum;
return get_sum(idx-1,l->l,r->l,x,p);
}
void dnc(LL s,LL e,LL l,LL r,bool p,bool q){
LL mid=(l+r)>>1;
LL i,di=s,dix=-1;
LL x,y;
LL a,b;
if(l>r) return;
for(i=s;i<=e;i++){
y=q?2*abs(st-i):abs(st-i);
if(mid-y<0) continue;
x=get_sum(29,tree[(p?st:i-1)],tree[(p?i:st-1)],mid-y,0);
if(x>dix){
dix=x;
di=i;
}
}
if(q){
if(p) e_tt[mid]=max(e_tt[mid],dix);
else s_tt[mid]=max(s_tt[mid],dix);
}else{
if(p) e_t[mid]=max(e_t[mid],dix);
else s_t[mid]=max(s_t[mid],dix);
}
dnc(s,di,l,mid-1,p,q);
dnc(di,e,mid+1,r,p,q);
}
int main(){
LL i,x;
scanf("%lld %lld %lld",&n,&st,&d);
tree[0]=new pst(0,0,NULL,NULL);tree[0]->l=tree[0]->r=tree[0];
for(i=1;i<=n;i++){
scanf("%lld",&x);
tree[i]=tree[i-1]->update(29,x);
if(i==st) dx=x;
}
dnc(1,st-1,0,d,false,true);
dnc(st+1,n,0,d,true,true);
dnc(1,st-1,0,d,false,false);
dnc(st+1,n,0,d,true,false);
ans=max(max(s_t[d-1]+dx,s_t[d]),max(e_t[d-1]+dx,e_t[d]));
for(i=0;i<=d;i++){
ans=max(ans,max(s_t[i]+e_tt[d-i],s_tt[i]+e_t[d-i]));
if(i!=d) ans=max(ans,max(s_t[i]+e_tt[d-i-1],s_tt[i]+e_t[d-i-1])+dx);
}
printf("%lld\n",ans);
return 0;
}