| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 657765 | lkh3happy | Holiday (IOI14_holiday) | C++14 | 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 <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
long long A[100001], t[400001], cnt[400001], ll=1, rr=0;
vector<long long> cp;
void upd(int l, int r, int n, int x, int v){
if(r<x || x<l) return;
if(l==r){
cnt[n]+=v; t[n]+=v*cp[l-1]; return;
}
int m=l+r>>1;
upd(l, m, n*2, x, v); upd(m+1, r, n*2+1, x, v);
t[n]=t[n*2]+t[n*2+1]; cnt[n]=cnt[n*2]+cnt[n*2+1];
}
long long kth(int l, int r, int n, int k){
if(l==r) return min(cnt[n], 1LL*k)*cp[l-1];
int m=l+r>>1;
if(cnt[n*2+1]>=k) return kth(m+1, r, n*2+1, k);
return kth(l, m, n*2, k-cnt[n*2+1])+t[n*2+1];
}
void move(int l, int r){
for(;rr<r;) upd(1, cp.size(), 1, A[++rr], 1);
for(;ll>l;) upd(1, cp.size(), 1, A[--ll], 1);
for(;rr>r;) upd(1, cp.size(), 1, A[rr--], -1);
for(;ll<l;) upd(1, cp.size(), 1, A[ll++], -1);
}
long long dnc(int l, int r, int s, int e, int st, int d){
if(r<l) return 0;
int m=l+r>>1;
long long mx=0, idx=e;
if(d-(m-st+m-e)>0){
move(e, m);
mx=kth(1, cp.size(), 1, d-(m-st+m-e)); idx=e;
for(int i=e-1;i>=s && d-(m-st+m-i);i--){
move(i, m);
if(mx<kth(1, cp.size(), 1, d-(m-st+m-i))) mx=kth(1, cp.size(), 1, d-(m-st+m-i)), idx=i;
}
}
return max(mx, max(dnc(l, m-1, s, idx, st, d), dnc(m+1, r, idx, e, st, d)));
}
long long solve(int n, int s, int d){
for(int i=0;i<=400000;i++) t[i]=cnt[i]=0; ll=1; rr=0;
return dnc(s, n, 1, s, s, d);
}
int main(){
int n, s, d;
scanf("%d%d%d", &n, &s, &d);
for(int i=1;i<=n;i++) scanf("%lld", &A[i]), cp.push_back(A[i]);
sort(cp.begin(), cp.end());
cp.erase(unique(cp.begin(), cp.end()), cp.end());
for(int i=1;i<=n;i++) A[i]=lower_bound(cp.begin(), cp.end(), A[i])-cp.begin()+1;
long long ans=solve(n, s, d);
reverse(A+1, A+n+1); s=n+1-s;
printf("%lld\n", max(ans, solve(n, s, d)));
return 0;
}