| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 696649 | 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>
using namespace std;
const int N=2e5+10;
vector<int>vec(1,0);
struct Persistent_Segment_Tree{
struct node{
int l,r,val;
long long sum;
node(){l=r=val=sum=0;}
};
node t[2000000];
int root[N],tot=0;
void upd(int &rt,int ort,int l,int r,int X,int d){
if(!rt)rt=++tot;
t[rt]=t[ort];
t[rt].val++;
t[rt].sum+=d;
if(l==r)return;
int mid=(l+r)>>1;
if(X<=mid)upd(t[rt].l=0,t[ort].l,l,mid,X,d);
else upd(t[rt].r=0,t[ort].r,mid+1,r,X,d);
}
long long ask(int rtl,int rtr,int l,int r,int k){
if(l==r)return 1ll*k*vec[l];
int mid=(l+r)>>1;
if(t[t[rtr].r].val-t[t[rtl].r].val>=k)return ask(t[rtl].r,t[rtr].r,mid+1,r,k);
return ask(t[rtl].l,t[rtr].l,l,mid,k-t[t[rtr].r].val+t[t[rtl].r].val)+t[t[rtr].r].sum-t[t[rtl].r].sum;
}
void clear(){
for(int i=0;i<=tot;i++)t[i]=node();
tot=0;
}
}tr;
long long ans;
int root[N],a[N];
int n,S,d;
void solve(int l,int r,int L,int R){
if(l>r)return;
int mid=(l+r)>>1;
long long pos=L,res=0;
for(int i=L;i<=R;++i){
long long val=tr.ask(root[mid-1],root[i],0,vec.size(),d-(2*(i-S)+S-mid));
if(val>=res)res=val,pos=i;
}
ans=max(ans,res);
solve(l,mid-1,L,pos),solve(mid+1,r,pos,R);
}
void sl(){
tr.clear();
for(int i=1;i<=n;i++)tr.upd(root[i]=0,root[i-1],0,vec.size(),lower_bound(vec.begin(),vec.end(),a[i])-vec.begin(),a[i]);
for(int i=1;i<=S;i++)ans=max(ans,tr.ask(root[i-1],root[S],0,vec.size(),d-S+i));
solve(1,S-1,S+1,n);
}
int main(){
scanf("%d%d%d",&n,&S,&d);
S++;
for(int i=1;i<=n;i++)scanf("%d",&a[i]),vec.push_back(a[i]);
sort(vec.begin(),vec.end());
vec.erase(unique(vec.begin(),vec.end()),vec.end());
sl(),S=n-S+1,reverse(a+1,a+n+1),sl();
printf("%lld",ans);
return 0;
}