| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 694420 | tommy1024 | 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.
#define _GLIBCXX_FILESYSTEM
#include <bits/stdc++.h>
#define all(v) (v).begin(),(v).end()
using namespace std;
typedef long long ll;
const ll LN=100005;
vector<ll> comp;
ll N,S,D,A[LN],C,ans;
struct node{
ll cnt,sum;
node *l,*r;
node(){
cnt=sum=0,l=r=nullptr;
}
};
node *root[LN];
void build(node *n,ll l,ll r){
if(l==r){
return;
}
ll m=(l+r)/2;
n->l=new node;n->r=new node;
build(n->l,l,m);build(n->r,m+1,r);
}
void add(ll p,node *prv,node *n,ll l,ll r){
if(l==r){
n->cnt=prv->cnt+1;
n->sum=prv->sum+comp[p];
return;
}
ll m=(l+r)/2;
if(p<=m){
n->l=new node;
n->r=prv->r;
add(p,prv->l,n->l,l,m);
}
else{
n->l=prv->l;
n->r=new node;
add(p,prv->r,n->r,m+1,r);
}
n->cnt=n->l->cnt+n->r->cnt;
n->sum=n->l->sum+n->r->sum;
}
ll query(ll k,node *n1,node *n2,ll l,ll r){
if(l==r){
return comp[l]*k;
}
ll m=(l+r)/2;
ll rcnt=n2->r->cnt-n1->r->cnt;
if(rcnt>=k){
return query(k,n1->r,n2->r,m+1,r);
}
else{
return n2->r->sum-n1->r->sum+query(k-rcnt,n1->l,n2->l,l,m);
}
}
void init(){
scanf("%lld%lld%lld",&N,&S,&D);
for(ll i=0;i<N;i++){
scanf("%lld",&A[i]);
comp.push_back(A[i]);
}
sort(all(comp));
comp.erase(unique(all(comp)),comp.end());
for(ll i=0;i<N;i++){
A[i]=lower_bound(all(comp),A[i])-comp.begin();
}
C=comp.size();
}
void f(ll s,ll e,ll l,ll r){
if(s>e||l>r)return;
ll m=(s+e)/2;
ll val=0,trk=l;
for(ll i=max(l,m);i<=r;i++){
ll k=D-(S+i-m*2); // 남은 거리
if(k>i-m+1)k=i-m+1; // 남은 도시
if(k<0)k=0;
ll sum=query(k,root[m],root[i+1],0,C-1);
if(sum>val)val=sum,trk=i;
}
ans=max(ans,val);
f(s,m-1,l,trk);f(m+1,e,trk,r);
}
void clr(){
root[0]=new node;
build(root[0],0,C-1);
for(ll i=0;i<N;i++){
root[i+1]=new node;
add(A[i],root[i],root[i+1],0,C-1);
}
}
void calc(){
clr();
f(0,S,0,N-1);
}
void solve(){
calc();
reverse(A,A+N);
S=N-1-S;
calc();
printf("%lld",ans);
}
int main()
{
init();
solve();
return 0;
}