| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1288908 | zangdo | 휴가 (IOI14_holiday) | C++17 | 0 ms | 0 KiB |
/******************************************************************************
Online C++ Compiler.
Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.
*******************************************************************************/
#include <bits/stdc++.h>
using namespace std;
const int MAXN =1e5 +5;
int arr[MAXN],pos[MAXN],pos1[MAXN], st, d,n;
bool cmp(int a,int b) {return arr[a]>arr[b];}
long long ST[4*MAXN + 5][2], f[(1<<18)+6],g[(1<<18)+6];
void up(int id, int l, int r, int u, long long on){
if(pos1[u]<l||pos1[u]>r){
return;
}
if(l==r) {ST[id][0]=arr[u]*on; ST[id][1]=on; return;}
int mid =(l+r)/2;
up(2*id, l,mid, u, on);
up(2*id+1, mid+1,r,u,on);
ST[id][0]=ST[2*id][0]+ST[2*id+1][0];
ST[id][1]=ST[2*id][1]+ST[2*id+1][1];
}
long long gsum(int id, int l,int r, int top,int accum){
if(l==r){
if(accum+ST[id][1]<=top) return ST[id][0];
else return 0;
}
int mid=(l+r)/2;
if(ST[2*id][1]+accum<=top) return ST[2*id][0]+gsum(2*id+1,mid+1,r,top,ST[2*id][1]+accum);
else return gsum(2*id,l,mid,top,accum);
}
void calf(int st, int l, int r, int l1, int r1,int bo){
//if(l>r) cerr<<"dcmm";
//cerr<<l<<' '<<r<<' '<<l1<<' '<<r1<<endl;
if(l1==r1){
up(1,1,n,st+l1,1);
for(int i=l;i<=r;i++) {
if(i>(bo*l1)) f[i] = gsum(1,1,n, i-bo*l1,0);
else f[i]=0;
}
return;
}
int mid =(l+r)/2, pos;
f[mid]=-1;
for(int i=l1;i<=r1;i++) {
up(1,1,n,st+i,1);
long long k;
if(mid>(bo*i)) k= gsum(1,1,n,mid-bo*i,0);
else k=0;
if(k>f[mid]) {pos= i; f[mid]=k;}
}
if(l==r) return;
for(int i=l1;i<=r1;i++) up(1,1,n,st+i,0);
calf(st, l,mid, l1,pos,bo);
calf(st,mid +1, r, pos,r1,bo);
}
void calfr(int st, int l, int r, int l1, int r1,int bo){
if(l1==r1){
up(1,1,n,st-l1,1);
for(int i=l;i<=r;i++) {
if(i>(bo*l1)) g[i] = gsum(1,1,n, i-bo*l1,0);
else g[i]=0;
}
return;
}
int mid =(l+r)/2, pos;
g[mid]=-1;
for(int i=l1;i<=r1;i++) {
up(1,1,n,st-i,1);
long long k;
if(mid>(bo*i)) k= gsum(1,1,n,mid-bo*i,0);
else k=0;
if(k>g[mid]) {pos= i; g[mid]=k;}
}
if(l==r) return;
for(int i=l1;i<=r1;i++) up(1,1,n,st-i,0);
calfr(st, l,mid, l1,pos,bo);
calfr(st,mid +1, r, pos,r1,bo);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>n>>st>>d; st++;
for(int i=1; i<=n;i++) {cin>>arr[i]; pos[i]=i;}
sort(pos+1, pos+n+1, cmp);
for(int i=1; i<=n;i++) pos1[pos[i]]=i;
long long ans=-1;
calf(st,1,1<<18,0,n-st,2);
//cout<<f[4]<<endl;
for(int i=1; i<=n;i++) up(1,1,n,i,0);
calfr(st,1,1<<18,0,st-1,2);
//cout<<g[4]<<endl;
ans=max(ans,max(g[d],f[d]));d--;
for(int i=1; i<=n;i++) up(1,1,n,i,0);
calf(st,1,1<<18,0,n-st,2);
for(int i=1; i<=n;i++) up(1,1,n,i,0);
calfr(st-1,1,1<<18,0,st-2,1);
for(int i=0;i<=d;i++) ans=max(ans,f[i]+g[d-i]);
for(int i=1; i<=n;i++) up(1,1,n,i,0);
calfr(st,1,1<<18,0,st-1,2);
for(int i=1; i<=n;i++) up(1,1,n,i,0);
calf(st+1,1,1<<18,0,n-st,1);
for(int i=0;i<=d;i++) ans=max(ans,f[i]+g[d-i]);
cout<<ans;
return 0;
}