| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 211750 | cgiosy | 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 "holiday.h"
using namespace std;
using ll=long long;
struct pst {
struct T { ll x; int cnt, l, r; };
int N, id=1, td=0;
vector<T> A;
vector<int> T;
pst(int sz): N(sz), A(N*32), T(N+1) {}
void add(int x, int s, int e, int&i) {
int p=i; i=++id;
A[i]={A[p].x+x, A[p].cnt+1, A[p].l, A[p].r};
if(s==e) return;
int m=s+e>>1;
if(x<=m) add(x, s, m, A[i].l);
else add(x, m+1, e, A[i].r);
}
void add(int x) { td++; add(x, 0, 1e9, T[td]=T[td-1]); }
ll sum(int k, int s, int e, int i, int j) {
if(s==e) {
int cnt=A[j].cnt-A[i].cnt;
if(!cnt) return 0;
return e*k;
}
int m=s+e>>1, n=A[A[j].r].cnt-A[A[i].r].cnt;
if(k<=n) return sum(k, m+1, e, A[i].r, A[j].r);
else return sum(k-n, s, m, A[i].l, A[j].l)+A[A[j].r].x-A[A[i].r].x;
}
ll sum(int l, int r, int k) {
return sum(k, 0, 1e9, T[l], T[r+1]);
}
};
ll findMaxAttraction(int N, int st, int M, int A[]) {
pst t(N);
for(int i=0; i<N; i++) t.add(A[i]);
function<ll(int, int, int, int)> f=
[&](int s, int e, int l, int r) {
if(l>r || s>e) return ll(0);
int m=s+e>>1;
pair<ll, int> n={0, 0};
for(int i=l; i<=r; i++) {
int a=st-m, b=i-st, k=M-(a+b+min(a, b));
n=max(n, {t.sum(m, i, k), i});
}
return max({n.first, f(s, m-1, l, n.second), f(m+1, e, n.second, r)});
};
return f(0, st-1, st-1, N-1);
}
int main() {
int N, M, st;
cin>>N>>st>>M;
vector<int> A(N);
for(int&x:A) cin>>x;
cout<<findMaxAttraction(N, st, M, &A[0]);
}