| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 199121 | red1108 | 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>
#include<ext/rope>
using namespace std;
using namespace __gnu_cxx;
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false);cin.tie(0)
#define fopen freopen("input.txt", "r", stdin)
#define eb emplace_back
#define em emplace
#define prec(a) cout<<fixed;cout.precision(a);
#define all(a) (a).begin(), (a).end()
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef tuple<int,int,int> tiii;
const ll INF = 2e16;
const int inf = 2e9;
template<class T>
void pr(T t) {cout << t << " ";}
template<class T, class ...Args>
void pr(T a, Args ...args) {cout << a << " ";pr(args...);}
template<class ...Args>
void prl(Args ...args) {pr(args...);cout << endl;}
int n, st, d, in[100010],p[100010],root[100010],si;
ll ans=0;
vector<pii> h;
struct Node{
int cnt,l,r;
ll sum;
Node(){cnt=sum=l=r=0;}
};
Node pst[2500000];
void add(int a, int b, int l, int r, int ind){
pst[b].cnt = pst[a].cnt + 1;
pst[b].sum = pst[a].sum + h[ind-1].fi;
pst[b].l = pst[a].l;pst[b].r = pst[a].r;
if(l==r) return ;
int m = (l+r)/2;
if(ind<=m){
pst[b].l = si;pst[si++]=Node();
add(pst[a].l,pst[b].l,l,m,ind);
}
else{
pst[b].r = si;pst[++si]=Node();
add(pst[a].r,pst[b].r,m+1,r,ind);
}
}
ll f(int a, int b, int l, int r, int k){
if((a==0&&b==0)||k==0) return 0;
int c = pst[pst[b].r].cnt-pst[pst[a].r].cnt;
if(l==r) return pst[b].sum-pst[a].sum;
if(c>=k) return f(pst[a].r,pst[b].r,(l+r)/2+1,r,k);
else return f(pst[a].l,pst[b].l,l,(l+r)/2,k-c)+(pst[pst[b].r].sum-pst[pst[a].r].sum);
}
void solve(int s, int e, int l, int r){
if(s>e) return ;
int m = (s+e)/2,ind=max((s+e)/2,l);
ll cur = 0;
for(int i = max(m,l);i<=r;i++){
int k = min(i-m+1, d - abs(m-st) - abs(i-m));
if(d<=0) break ;
ll t = f(root[m-1],root[i],1,n,k);
if(cur<=t){
cur = t;
ind = i;
}
}
ans = max(ans, cur);
solve(s,m-1,l,ind);
solve(m+1,e,ind,r);
}
void calc(){
si=1;
//prl("hi");
for(int i=1;i<=n;i++){
//prl("i=",i,"val=",h[p[i]-1].fi);
root[i] = si;
pst[si++]=Node();
add(root[i-1], root[i], 1, n, p[i]);
assert(si<2500000);
}
//prl("debug:",f(root[1],root[3],1,n,1));
solve(1,n,1,n);
}
int main(){
cin>>n>>st>>d;
for(int i=1;i<=n;i++){
cin>>in[i];
h.eb(in[i],i);
}
sort(h.begin(), h.end());
for(int i=0;i<h.size();i++) p[h[i].se]=i+1;
calc();
reverse(in+1,in+n+1);
reverse(p+1,p+n+1);
st = n-st+1;
calc();
cout<<ans;
}