| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 522961 | ftkbrian | 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<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pll pair<ll,ll>
#define f first
#define s second
bool offline;
ll n,d;
ll A[101010];
vector<ll> V;
ll idx(ll v) { return lower_bound(V.begin(),V.end(),v)-V.begin()+1; }
pll ST[404040];
pll hap(pll a,pll b) { return {a.f+b.f,a.s+b.s}; }
void upd(ll id,ll s,ll e,ll t,ll v) {
if(s > t || t > e) return;
if(s == e) { ST[id].f += v; ST[id].s++; return; }
ll m = s+e>>1;
upd(id*2,s,m,t,v); upd(id*2+1,m+1,e,t,v);
ST[id] = hap(ST[id*2],ST[id*2+1]);
}
ll query(ll id,ll s,ll e,ll lft) {
if(s == e) {
if(ST[id].s == 0) return 0;
return ST[id].f/ST[id].s*min(ST[id].s,lft);
}
ll m = s+e>>1;
if(ST[id*2+1].s < lft) return ST[id*2+1].f+query(id*2,s,m,lft-ST[id*2+1].s);
return query(id*2+1,m+1,e,lft);
}
ll st;///시작점
ll ans;
ll dist(ll a,ll b,ll c) { return c-a+max(0ll,min(c-b,b-a)); }
void DnC(ll s,ll e,ll qs,ll qe) {
if(s > e) return;
ll m = s+e>>1; V.clear();
ll opt = qs,val = -1;
for(int i = m ; i <= qe ; i++) {
if(dist(m,st,i) > d) break;
V.push_back(A[i]);
}
sort(V.begin(),V.end());
V.erase(unique(V.begin(),V.end()),V.end());
ll sz = V.size();
for(int i = 1 ; i <= 4*sz ; i++) ST[i] = {0,0};
for(int i = m ; i < qs ; i++) upd(1,1,sz,idx(A[i]),A[i]);
for(int i = qs ; i <= qe ; i++) {
ll v = d-dist(m,st,i);
if(v <= 0) break;
upd(1,1,sz,idx(A[i]),A[i]);
ll vl = query(1,1,sz,v);
if(val < vl) opt = i,val = vl;
}
ans = max(ans,val);
DnC(s,m-1,qs,opt);
DnC(m+1,e,opt,qe);
}
main() {
if(offline) freopen("input.txt","r",stdin);
ios_base::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n>>st>>d; st++;
for(int i = 1 ; i <= n ; i++) cin>>A[i];
DnC(1,st,st,n);
cout<<ans<<"\n";
}