| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 563683 | gs15120 | 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 <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <cassert>
#include <thread>
#include <tuple>
#include <typeindex>
using namespace std;
#define ll long long
#define lll long long//__int128
#define pii pair<int,int>
#define pdi pair<double,int>
#define f first
#define s second
# define PI 3.14159265358979323846
struct P
{
int x[2],c;
ll s;
/*bool operator <(const P &a) const
{
//if(y!=a.y)
//return y<a.y;
return y<a.y;
}*/
};
//vector<P>
int nd=0;
P psg[2222222];
int mx=1000000000;
int a,b,c,s;
int o[111111],rt[111111];
//P sg[113333][22];
vector<int> v;
map<int,int> mp;
ll ans=0,d;
int nw()
{
nd++;
if(nd>=2222222) assert(0);
int n=nd;
//psg.push_back({});
return n;
}
void add(int p,int i,int n,int m,int k)
{
//if(k<n||m>k) return;
psg[i]=psg[p];
psg[i].c++;
psg[i].s+=v[k];
if(n==m) return;
int e=0;
if(k>(n+m)/2) e=1;
int dd=nw();
psg[i].x[e]=dd;
if(k<=(n+m)/2) add(psg[p].x[e],psg[i].x[e],n,(n+m)/2,k);
else add(psg[p].x[e],psg[i].x[e],(n+m)/2+1,m,k);
}
ll get(int p,int i,int n,int m,ll k)
{
if(psg[i].c-psg[p].c<=k) return psg[i].s-psg[p].s;
if(n==m) return k*n;
int c=psg[psg[i].x[1]].c-psg[psg[p].x[1]].c;
if(c>=k) return get(psg[p].x[1],psg[i].x[1],(n+m)/2+1,m,k);
return get(psg[p].x[1],psg[i].x[1],(n+m)/2+1,m,c)+get(psg[p].x[0],psg[i].x[0],n,(n+m)/2,k-c);
}
void lf(int n,int m,int x,int y)
{
if(n>m) return;
int h=(n+m)/2;
//x=s,y=a;
if((s-h)*2+(x-s)>d)
{
lf(h+1,m,x,y);
return;
}
//printf("%d %d %d %d\n",n,m,x,y);
ll k=-1987654321987654321;
int p=x;
for(int i=x;d-(s-h)*2-(i-s)>=0&&i<=y;i++)
{
ll z=get(rt[h-1],rt[i],0,mx,d-(s-h)*2-(i-s));
if(z>k) k=z,p=i;
}
ans=max(ans,k);
lf(n,h-1,x,p);
lf(h+1,m,p,y);
}
void rr(int n,int m,int x,int y)
{
if(n>m) return;
//x=1,y=s;
int h=(n+m)/2;
if((h-s)*2+(s-y)>d)
{
rr(n,h-1,x,y);
return;
}
ll k=-1987654321987654321;
int p=y;
for(int i=y;d-(h-s)*2-(s-i)>=0&&i>=x;i--)
{
ll z=get(rt[i-1],rt[h],0,mx,d-(h-s)*2-(s-i));
if(z>k) k=z,p=i;
}
ans=max(ans,k);
rr(n,h-1,x,p);
rr(h+1,m,p,y);
}
int main()
{
//psg.push_back({});
scanf("%d %d %lld",&a,&s,&d);
s++;
for(int t=1;t<=a;t++)
{
scanf("%d",&o[t]);
v.push_back(o[t]);
}
sort(v.begin(),v.end());
v.resize(unique(v.begin(),v.end())-v.begin());
for(int h=0;h<v.size();h++)
mp[v[h]]=h;
mx=v.size()-1;
for(int t=1;t<=a;t++)
{
int nn=nw();
rt[t]=nn;
add(rt[t-1],rt[t],0,mx,mp[o[t]]);
}
lf(1,s,s,a);
rr(s,a,1,s);
printf("%lld",ans);
//printf("%lld",get(rt[3],rt[5],0,mx,1));
}