| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 881263 | 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 int long long
using namespace std;
const int N=3e5, inf = 1e18;
int f[N+1], fr[N+1], g[N+1], gl[N+1];
int a[N+1], n, start, d, id[N+1], pos[N+1];
struct segtree
{
int val=0, cnt=0;
int low, hi;
segtree* l;
segtree* r;
void init(int __low, int __hi)
{
val=0, cnt=0;
low=__low;
hi=__hi;
int mid =low+hi>>1;
if(low!=hi)
{
l= new segtree;
r= new segtree;
l->init(low, mid);
r->init(mid+1, hi);
}
}
void update(int i, int k, int t)
{
if(low==hi)
{
val+=k, cnt+=t;
return;
}
int mid=low+hi>>1;
if(i<=mid) l->update(i,k,t);
else r->update(i,k,t);
val=l->val+r->val;
cnt=l->cnt+r->cnt;
}
int get(int k)
{
if(low==hi)
{
if(k>0) return val;
else return 0;
}
if(r->cnt>=k) return r->get(k);
else return r->val + l->get(k-r->cnt);
}
}base;
void dnaf(int l, int r, int mn, int mx, int st)
{
if(l>r) return;
int mid=l+r>>1;
//cout << mid << " " <<l << " " << r <<" " << mn << " " << mx << '\n';
//cout << base.val << '\n';
for(int i=mn;i<=min(st+mid,mx);++i)
{
base.update(pos[i], a[i], 1);
// cout << base.val << " ";
int cnt = mid-(i-st);
int k = base.get(cnt);
if(k>f[mid])
{
f[mid]=k;
fr[mid]=i;
}
}
// cout << '\n';
// cout << fr[mid] << " " << f[mid] << '\n' << '\n';
for(int i = min(st+mid,mx); i>=fr[mid];--i) base.update(pos[i], -a[i], -1);
dnaf(mid+1,r, fr[mid], mx, st);
for(int i=mn;i<fr[mid];++i) base.update(pos[i], -a[i], -1);
dnaf(l,mid-1, mn, fr[mid], st);
}
void dnag(int l, int r, int mx, int mn, int st)
{
if(l>r) return;
int mid=l+r>>1;
//cout << mid << " " <<l << " " << r <<" " << mn << " " << mx << '\n';
//cout << base.val << '\n';
for(int i=mx;i>=max(st-mid,mn);--i)
{
base.update(pos[i], a[i], 1);
//cout << base.val << " ";
int cnt = mid-(st-i);
int k = base.get(cnt);
if(k>g[mid])
{
g[mid]=k;
gl[mid]=i;
}
}
//cout << '\n';
//cout << gl[mid] << " " << g[mid] << '\n' << '\n';
for(int i = max(st-mid,mn); i<=gl[mid];++i) base.update(pos[i], -a[i], -1);
dnag(l,mid-1, gl[mid], mn, st);
for(int i=mx;i>gl[mid];--i) base.update(pos[i], -a[i], -1);
dnag(mid+1,r, mx, gl[mid], st);
}
bool ss(int x, int y)
{
return a[x]<a[y];
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n >> start >> d;
start++;
for(int i=1;i<=n;++i)
{
cin >> a[i];
id[i]=i;
}
base.init(1, n);
sort(id+1,id+n+1, ss);
for(int i=1;i<=n;++i)
{
pos[id[i]]=i;
}
dnaf(0, d, start, n, start);
// for(int i=0;i<=d;++i) cout << i << " " << fr[i] << " " << f[i] << '\n';
//cout << base.val << '\n';
base.init(1,n);
// cout << "L";
dnag(0, d, start-1, 1, start-1);
// cout << '\n';
// for(int i=0;i<=d;++i) cout << i << " " << gl[i] << " " << g[i] << '\n';
int ans=0;
for(int i=0;i<=d;++i)
{
ans = max(ans, f[i] + g[d-i-(fr[i]-start+1)]);
}
fill(g,g+d+1,0);
fill(f,f+d+1,0);
fill(gl,gl+d+1,0);
fill(fr,fr+d+1,0);
base.init(1,n);
dnag(0, d, start, 1, start);
base.init(1,n);
dnaf(0, d, start+1, n, start+1);
for(int i=0;i<=d;++i)
{
ans = max(ans, g[i] + f[d-i-(start+1-gl[i])]);
}
cout << ans;
}