| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 696665 | 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>
using namespace std;
template <typename T> inline void read(T &x)
{
x=0;T f=1;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-')f=-1;
for(;isdigit(c);c=getchar()) x=(x<<1)+(x<<3)+(c^48);
x*=f;
}
template <typename T,typename ...Args>void read(T &x,Args&...args){read(x),read(args...);}
template <typename T> void print(T x)
{
if(x<0) x=-x,putchar('-');
if(x>9) print(x/10);
putchar(x%10+48);
}
template <typename T> void print(T x,char c){print(x); putchar(c);}
template<typename T>inline void output(T x){print(x,' ');}
template<typename T,typename ...Arg>inline void output(T x,Arg ...arg){output(x);output(arg...);}
const int N=100007;
int n,m,s,d,a[N],root[N]; long long ans,fl[N<<1],fr[N<<1],gl[N<<1],gr[N<<1];
template<typename T>struct LSH
{
vector<T>v;
void add(T x){v.push_back(x);}
void build()
{
sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()),v.end());
}
int ask(T x){return lower_bound(v.begin(),v.end(),x)-v.begin();}
int size(){return v.size();}
void clear(){v.clear();}
}; LSH<int>lsh;
struct segment_tree
{
int f0[N<<4],ls[N<<4],rs[N<<4],tot; long long f1[N<<4];
int New(int v0,int v1,int l,int r)
{
tot++;
f0[tot]=v0,f1[tot]=v1;
ls[tot]=l; rs[tot]=r;
return tot;
}
void pushup(int rt)
{
f0[rt]=f0[ls[rt]]+f0[rs[rt]];
f1[rt]=f1[ls[rt]]+f1[rs[rt]];
}
void update(int &rt,int l,int r,int x)
{
rt=New(f0[rt],f1[rt],ls[rt],rs[rt]);
if(l==r) return f0[rt]++,f1[rt]+=lsh.v[x],void();
int mid=(l+r)>>1;
if(x<=mid) update(ls[rt],l,mid,x);
else update(rs[rt],mid+1,r,x);
pushup(rt);
}
long long ask(int rt1,int rt2,int l,int r,int num)
{
if(l==r) return 1ll*lsh.v[l]*min(f0[rt2]-f0[rt1],num);
int mid=(l+r)>>1,now=f0[rs[rt2]]-f0[rs[rt1]];
if(now>=num) return ask(rs[rt1],rs[rt2],mid+1,r,num);
else return f1[rs[rt2]]-f1[rs[rt1]]+ask(ls[rt1],ls[rt2],l,mid,num-now);
}
}Tree;
void solve1(int l,int r,int L,int R)
{
if(l>r||L>R) return;
int mid=(l+r)>>1,Mid=L; long long now=0;
for(int i=L;i<=min({R,mid,n-s});i++)
{
now=Tree.ask(root[s-1],root[s+i],0,m-1,mid-i);
if(now>fr[mid]) fr[mid]=now,Mid=i;
}
solve1(l,mid-1,L,Mid);
solve1(mid+1,r,Mid,R);
}
void solve2(int l,int r,int L,int R)
{
if(l>r)return;
int mid=(l+r)>>1,Mid=L; long long now=0;
for(int i=L;i<=min({R,mid/2,n-s});i++)
{
now=Tree.ask(root[s-1],root[s+i],0,m-1,mid-i*2);
if(now>gr[mid])gr[mid]=now,Mid=i;
}
solve2(l,mid-1,L,Mid);
solve2(mid+1,r,Mid,R);
}
void solve3(int l,int r,int L,int R)
{
if(l>r)return;
int mid=(l+r)>>1,Mid=L; long long now;
for(int i=L;i<=min({R,mid,s-1});i++)
{
now=Tree.ask(root[s-i-1],root[s-1],0,m-1,mid-i);
if(now>fl[mid])fl[mid]=now,Mid=i;
}
solve3(l,mid-1,L,Mid);
solve3(mid+1,r,Mid,R);
}
void solve4(int l,int r,int L,int R)
{
if(l>r)return;
int mid=(l+r)>>1,Mid=L; long long now;
for(int i=L;i<=min({R,mid/2,s-1});i++)
{
now=Tree.ask(root[s-i-1],root[s-1],0,m-1,mid-i*2);
if(now>gl[mid])gl[mid]=now,Mid=i;
}
solve4(l,mid-1,L,Mid);
solve4(mid+1,r,Mid,R);
}
int main()
{
read(n,s,d); s++;
for(int i=1;i<=n;i++)
read(a[i]),lsh.add(a[i]);
lsh.build(); m=lsh.size();
for(int i=1;i<=n;i++)
a[i]=lsh.ask(a[i]);
for(int i=1;i<=n;i++)
Tree.update(root[i]=root[i-1],0,m-1,a[i]);
solve1(1,d,0,n-s);
solve2(1,d,0,n-s);
solve3(1,d,0,s-1);
solve4(1,d,0,s-1);
for(int i=0;i<=d;i++)
ans=max(ans,max(fl[i]+gr[d-i],gl[i]+fr[d-i]));
print(ans,'\n');
return 0;
}