| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 696140 | vjudge1 | Holiday (IOI14_holiday) | C++14 | 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 ll long long
using namespace std;
int n,st,d,a[201000],T[201000];
ll su2[6010000];int su[6001000],c,ls[6001000],rs[6001000];
const int I=1e9;
void up(int &o,int lst,int l,int r,int x){
o=++c;
su2[o]=su2[lst]+x,su[o]=su[lst]+1,ls[o]=ls[lst],rs[o]=rs[lst];
if(l==r)return;
int mid=(l+r)>>1;
if(x<=mid)up(ls[o],ls[lst],l,mid,x);
else up(rs[o],rs[lst],mid+1,r,x);
}
ll kth(int o1,int o2,int l,int r,int k){
if(l==r)return 1ll*min(su[o1]-su[o2],k)*l;
int mid=(l+r)>>1,z=su[rs[o1]]-su[rs[o2]];
if(k<=z)return kth(rs[o1],rs[o2],mid+1,r,k);
return (su2[rs[o1]]-su2[rs[o2]])+kth(ls[o1],ls[o2],l,mid,k-z);
}
ll calc(int l,int r){
int k=2*(r-st)+(st-l);
if(k<d)return kth(T[r],T[l-1],0,I,d-k);
return 0;
}
ll ans;
void cdq(int l,int r,int pl,int pr){
if(l>r||pl>pr)return;
int ip=-1,mid=(l+r)>>1;
ll M=-1;
for(int i=pl;i<=pr;i++){
ll V=calc(mid,i);
if(M<V)M=V,ip=i;
}
ans=max(ans,M);
cdq(l,mid-1,pl,ip),cdq(mid+1,r,ip,pr);
}
void sol(){
c=0;
for(int i=1;i<=n;i++)up(T[i],T[i-1],0,I,a[i]);
cdq(1,st,st,n);
}
int main(){
scanf("%d%d%d",&n,&st,&d);st++;
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
sol();
st=n-st+1,reverse(a+1,a+n+1);sol();
return printf("%lld",ans),0;
}