| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 697310 | vjudge1 | 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 LL long long
using namespace std;
void read(int &x){
x=0;char ch=getchar();int f=1;
while((ch<'0'||ch>'9')&&ch!=45)ch=getchar();
if(ch==45)ch=getchar(),f=-1;
while(ch<='9'&&ch>='0')x=x*10+ch-'0',ch=getchar();
x*=f;
}
template<typename T1,typename T2>void cmax(T1 &x,const T2 &y){if(y>x)x=y;}
template<typename T1,typename T2>void cmin(T1 &x,const T2 &y){if(y<x)x=y;}
const int N=3e5+10;
int m;
int b[N];
LL ans[N];
struct KthTree{
struct node{
LL sz,sm;
}a[N<<2];
int rk[N];
void build(int l,int r,int rt){
if(l==r){
rk[l]=rt;
return ;
}
int mid=l+r>>1;
build(l,mid,rt<<1);
build(mid+1,r,rt<<1|1);
}
void clear(){
// printf("CLEAR\n");
build(1,m,1);
memset(a,0,sizeof(a));
}
void upd(int rt,int x){
while(rt)a[rt].sz++,a[rt].sm+=b[x],rt>>=1;
}
LL query(int l,int r,int rt,int k){
if(a[rt].sz<=k)return a[rt].sm;
if(l==r)return b[l]*k;
int mid=l+r>>1;
if(a[rt<<1|1].sz<k)return query(l,mid,rt<<1,k-a[rt<<1|1].sz)+a[rt<<1|1].sm;
return query(mid+1,r,rt<<1|1,k);
}
void insert(int x){
// printf("INSERT %d\n",x);
int pos=lower_bound(b+1,b+m+1,x)-b;
upd(rk[pos],pos);
}
LL qry(int k){
if(k<=0)return 0;
auto res=query(1,m,1,k);
// printf("query %d %lld\n",k,res);
return res;
}
}T;
vector<LL> solve(vector<int> a,int d,int c,int ex=0){
memset(ans,0,sizeof(ans));
queue<tuple<int,int,int,int>> q1,q2;
q2.push(make_tuple(1,d,1,a.size()-1));
while(!q2.empty()){
swap(q1,q2);T.clear();
int p=-1;
while(!q1.empty()){
auto [l1,r1,l2,r2]=q1.front();q1.pop();
LL mid=l1+r1>>1,val=-1,pos=0;
auto upd=[&](int x){
LL res=T.qry(mid-c*(x+ex));
if(res>val)val=res,pos=x;
};
upd(p);
while(p+1<=r2){
T.insert(a[++p]);
upd(p);
}
ans[mid]=val;
if(mid-1>=l1)q2.push(make_tuple(l1,mid-1,l2,pos));
if(r1>=mid+1)q2.push(make_tuple(mid+1,r1,pos,r2));
}
}
return vector<LL>(ans,ans+d+1);
}
signed main(){
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
//freopen(".in","w",stdout);
int i,n,start,d;
LL ans=0;
vector<int> a;
read(n),read(start),read(d);
a.resize(n);
for(i=0;i<n;i++)read(a[i]),b[i+1]=a[i];
sort(b+1,b+1+n);m=unique(b+1,b+n+1)-b-1;
for(int o=0;o<=1;o++){
auto f=solve(vector<int>(a.begin()+start,a.end()),d,o?1:2);
vector<int> w(a.begin(),a.begin()+start);
reverse(w.begin(),w.end());
auto g=solve(w,d,o?2:1,1);
for(i=0;i<=d;i++)cmax(ans,f[i]+g[d-i]);
}
cout<<ans<<endl;
return 0;
}