| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 549833 | lobo_prix | 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.
//[Author] tuxedcat
//[Date] 2022.04.17
//[File] src/holiday.cpp
//[Library] https://github.com/tuxedcat/pslib
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define _EXT_CODECVT_SPECIALIZATIONS_H 1
#define _EXT_ENC_FILEBUF_H 1
#include <bits/extc++.h>
using namespace std;
#define int i64
#define FP_EPS 1e-11
#define COUT_FP 11
using f64=double; //long double(살짝느림),__float128(매우느림)
// #define CPP20 1
#define DBG_SETW 3
// #define endl '\n' //remove it when interactive
#define fi first
#define se second
#define mkp make_pair
#define mkt make_tuple
#define lb lower_bound
#define ub upper_bound
#define bs binary_search
#define itos to_string
#define head(x) (x.begin())
#define tail(x) prev(x.end())
using i64=long long;using u64=unsigned long long;using u32=unsigned;
using pint=pair<int,int>;using tint=tuple<int,int,int>;
template<class T>using Str=basic_string<T>;
template<class T,class CMP=less<>>using PQ=std::priority_queue<T,vector<T>,CMP>;
//functions before include <arr.h>
//Math
#if !(CPP20)
#define countl_zero(x) __builtin_clzll(x)
#define popcount(x) __builtin_popcountll(x)
#define bit_ceil(x) 1<<clg2(x)
#endif
#if CPP20
// #define sz ssize
template<class T>int sz(const T& x){return x.size();}
#else
template<class T>int sz(const T& x){return x.size();}
#endif
int fdiv(int a,int b){if(b<0)a=-a,b=-b;return (a>0)?a/b:(a-b+1)/b;}
int cdiv(int a,int b){if(b<0)a=-a,b=-b;return (a>0)?(a+b-1)/b:a/b;}
i64 flg2(u64 x){return 63-countl_zero(x);}
i64 clg2(u64 x){return x-1==0?0:64-countl_zero(x-1);}
int fsqrt(i64 n) {i64 i=1;while(i*i<=n)i++;return i-1;}
int csqrt(i64 n) {i64 i=1;while(i*i<n)i++;return i;}
template<class T>T sq(T x){return x*x;}
template<class T>constexpr T inf(){return numeric_limits<T>::max()/2;}
template<class T>constexpr T nan(){return inf<T>()+1;}
#ifdef CPP20
template<typename T> concept MemberInf=requires(T t){t.inf();};
template<typename T> concept MemberNan=requires(T t){t.nan();};
template<MemberInf T>T inf(){return T().inf();}
template<MemberNan T>T nan(){return T().nan();}
#endif
//IO & misc
template<class...A>void print(A...a){((cout<<a),...);}
template<class...A>void println(A...a){((cout<<a),...,(cout<<endl));}
template<class T=int>T input(){T x;cin>>x;return x;}
template<class T,class U>bool assmin(T& a,U&& b){return a>b?a=b,true:false;}
template<class T,class U>bool assmax(T& a,U&& b){return a<b?a=b,true:false;}
void MUST(bool expr){
#if DEBUG
#include <csignal>
if(!expr)
raise(SIGINT);
#endif
}
#define ARG(...) __VA_ARGS__
#define func(RetT,fname,...) function<RetT(__VA_ARGS__)> fname=[&](__VA_ARGS__)->RetT
#define lam(expr,...) [&](__VA_ARGS__){return expr;}
#define lamp(expr,...) [](__VA_ARGS__){return expr;}
template<class T, class P=vector<T>>
struct Arr:public P{
Arr(){P::shrink_to_fit();}
explicit Arr(signed n):P(n){}
explicit Arr(signed n,T init):P(n,init){}
Arr(initializer_list<T>il):P(il){}
Arr(auto its, auto ite):P(its,ite){}
inline T& operator[](signed i){
int n=sz(*this);
if(i<0)i+=n,dbg1("Neg Index Found");
if(i>=n)i-=n,dbg1("Over Index Found");
return P::operator[](i);
}
const T& operator[](signed i)const{
int n=sz(*this);
if(i<0)i+=n,dbg1("Neg Index Found");
if(i>=n)i-=n,dbg1("Over Index Found");
return P::operator[](i);
}
T& at(signed i){return *this[i];}
const T& at(signed i)const{return *this[i];}
};
template<class... A> auto ARR(auto n,A&&... a)
{if constexpr(!sizeof...(a)) return n; else return Arr(n,ARR(a...));}
//Consts
// const f64 pi=numbers::pi_v<f64>,eps=FP_EPS;
const f64 pi=acos(-1),eps=FP_EPS;
const int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
//functions after include <arr.h>
template<class T>int argmin(const Arr<T>& a){return min_element(a.begin(),a.end())-a.begin();}
template<class T>int argmax(const Arr<T>& a){return max_element(a.begin(),a.end())-a.begin();}
Arr<int> permuinv(const Arr<int>& a){Arr<int> r(sz(a));for(int i=0;i<sz(a);i++)r[a[i]]=i;return r;}
template<class T>map<T,Arr<int>> classify(const Arr<T>& a){
map<T,Arr<int>> r;
for(int i=0;i<sz(a);i++)
r[a[i]].push_back(i);
return r;
}
//Pre-runs
#if !(DEBUG)
auto __PR1=(ios::sync_with_stdio(0),cin.tie(0),cout.tie(0));
#endif
auto& __PR2=(cout<<fixed<<setprecision(COUT_FP));
//
#ifdef CPP20
template<typename T>
concept Monoid=requires(T t){
T::f(T::id(),T::id());
T::fn(T::id(),0);
//T::T;
};
#else
#define Monoid class
#endif
template<class T, class M> T fn(T x,int n){
//f(...f(f(id,x),x),...,x) n겹 O(log(n))
if(!n)return M::id();
T res=fn<T,M>(x,n/2);
return n%2?M::f(M::f(res,res),x):M::f(res,res);
}
template<class T>struct MAdd{
static T id(){return T(0);}
static T f(T x,T y){return x+y;}
static T fn(T x,int n){return x*n;}
};
template<class T>struct MMul{
static T id(){return T(1);}
static T f(T x,T y){return x*y;}
static T fn(T x,int n){return ::fn<T,MMul<T>>(x,n);}
};
template<class T>struct MAss{
static T id(){return nan<T>();}
static T f(T x,T y){return y==id()?x:y;}
static T fn(T x,int n){return x;}
};
template<class T>struct MMin{
static T id(){return inf<T>();}
static T f(T x,T y){return min(x,y);}
static T fn(T x,int n){return x;}
};
template<class T>struct MMax{
static T id(){return -inf<T>();}
static T f(T x,T y){return max(x,y);}
static T fn(T x,int n){return x;}
};
template<class T>struct MXor{
static T id(){return T(0);}
static T f(T x,T y){return x^y;}
static T fn(T x,int n){return n%2?x:0;}
};
template<class T>struct MGcd{
static T id(){return T(0);}
static T f(T x,T y){return gcd(x,y);}
static T fn(T x,int n){return x;}
};
template<class T>struct MFunc{
static T id(){return T();}
static T f(T x,T y){return x.f(y);}
static T fn(T x,int n){return ::fn<T,MFunc<T>>(x,n);}
};
#ifdef CPP20
//NOTE: non-empty. empty-able일시 max(0,val.m)하면 됨
struct TMaxSubArr{
int s=0,l=-inf<int>(),m=-inf<int>(),r=-inf<int>();
TMaxSubArr f(TMaxSubArr x)const{return {s+x.s,max(l,s+x.l),max({m,r+x.l,x.m}),max(r+x.s,x.r)};}
TMaxSubArr nan()const{return {::nan<int>(),::nan<int>(),::nan<int>(),::nan<int>()};}
friend strong_ordering operator<=>(const TMaxSubArr&,const TMaxSubArr&)=default;
TMaxSubArr rev()const{return {s,r,m,l};}//for commutativeless query, refer boj13519
};
template<Monoid M>
auto scanl(auto s,auto e){
using T=decltype(M::id()); int n=e-s;
Arr<T> b={M::id()};
while(s!=e)
b.emplace_back(M::f(b.back(),*s++));
rotate(b.begin(),b.begin()+1,b.end());
return b;
}
template<Monoid M>
auto scanr(auto s,auto e){
using T=decltype(M::id()); int n=e-s;
Arr<T> b={M::id()};
while(s!=e)
b.emplace_back(M::f(b.back(),*--e));
reverse(b.begin(),b.end());
return b;
}
#endif
template<Monoid Q,auto fupd,int xlo=0,int xhi=inf<signed>()> struct SegPersi{
using T=decltype(Q::id());
T v=Q::id();
SegPersi *l{},*r{};
~SegPersi(){/*double free?*/}
SegPersi* upd(int i,T x,int cs=xlo,int ce=xhi){
if(ce<=i or i+1<=cs) return this;
if(i<=cs and ce<=i+1) return new SegPersi{fupd(v,x)};
int cm=(cs+ce)/2;
if(!l)l=new SegPersi;
if(!r)r=new SegPersi;
auto ret=new SegPersi;
ret->l=l->upd(i,x,cs,cm);
ret->r=r->upd(i,x,cm,ce);
ret->v=Q::f(ret->l->v,ret->r->v);
return ret;
}
T q(int s,int e, int cs=xlo, int ce=xhi){
if(ce<=s or e<=cs)return Q::id();
if(s<=cs and ce<=e) return v;
int cm=(cs+ce)/2;
if(!l)l=new SegPersi;
if(!r)r=new SegPersi;
return Q::f(l->q(s,e,cs,cm),r->q(s,e,cm,ce));
}
};
//USAGE: boj.kr/14898
//USAGE: https://codeforces.com/contest/961/submission/100706299
//d[i][j] = min{-1<=k<=j}(d[i-1][k]+c[k+1][j+1]
//i: 전체 dp단계
//j: 현재 dp단계의 계산할 index
//k: 현재 d[i][j]를 계산하는데 사용하는 iter변수.
//k의 범위는 j를 포함하지 않음에 주의(필요하면 포함시키는등 수정필요할수 있음)
//k in [-1,j]로 하고 dp와 cost가 둘다 길이0인 구간을 지원하도록 하는게 맞을듯?
//d: dp배열. -1인 인덱스를 지원해야함.
//c: cost함수. c(s,e)로 반열린구간[s,e)의 코스트를 의미. 길이0인 구간을 지원해야함
//아래는 아직 검증안한 옛날메모
//opt[i][j]≤opt[i][j+1]을 만족할때 사용가능. opt[i][j]는 dp[i][j]점화식에서 최적인 k값
//충분조건: a<b,c<d -> f(a,c)+f(b,d)<=f(a,d)+f(b,c) (사각부등식보다 강력) (boj14636)
//a[j]=min{k<j}(b[k]+c[k][j])를 계산함. a=d[i], b=d[i-1]로 두면 됨
void dnc(Arr<int>& a,const Arr<int>& b,function<int(int,int)> c,int s,int e,int ks,int ke){
if(e-s<=0)return;
int m=(s+e)/2,km=ks;
for(int k=ks;k<ke;k++)
if(a[m]>b[k]+c(k+1,m+1))
a[m]=b[k]+c(k+1,m+1),km=k;
dnc(a,b,c,s,m,ks,km+1),dnc(a,b,c,m+1,e,km,ke);
}
void dnc(Arr<int>& a,const Arr<int>& b,function<int(int,int)> c,int s,int e){dnc(a,b,c,s,e,s-1,e);}
struct A{
int cnt,sum;
A(int cnt=0,int sum=0):cnt(cnt),sum(sum){}
A operator+(A o)const{return {cnt+o.cnt,sum+o.sum};}
};
using PST=SegPersi<MAdd<A>,lamp(y,A x,A y),0,3333>;
//NOTE: monge는 아니지만 opt단조성이 있어서 최적화 가능
int calc(Arr<int> a,int p,int d){
int n=sz(a);
//처음 생각: 큰 수부터 업뎃해 버전만들면 버전이분탐색으로 log^2
//개선(서다수쿼pst와 비슷)된 생각: 그냥 수열 인덱스와 같은 버전생성 후 Q_r(0,k)-Q_l(0,k) bin_lift하면 log에 가능
//근데 쿼리가 각각 버전마다 나뉘어져 있어서 리프팅은 코드를 따로 짜야할듯 그냥 로그제곱 시도해보자.
Arr<int> o(n);
iota(o.begin(),o.end(),0);
sort(o.begin(),o.end(),lam(a[i]>a[j],int i,int j));
Arr<PST*> ver(n+1);
ver[-1]=new PST;
for(int i=0;i<n;i++)
ver[i]=ver[i-1]->upd(o[i],{1,a[o[i]]});
func(int,f,int s,int e){
int move=abs(p-s)+e-s-1;
int c=min<int>(d-move,e-s);
//TODO: select largest c numbers in [s,e)
int ss=-1,ee=n-1;
while(ee-ss>1){
int mm=(ss+ee)/2;
if(ver[mm]->q(s,e).cnt<c) ss=mm;
else ee=mm;
}
return -ver[ee]->q(s,e).sum;
};
Arr<int> arr(n+1);
dnc(arr,Arr<int>(n+1),f,0,n);
return -*min_element(arr.begin(),arr.end());
}
void solve(){
int n,p,d; cin>>n>>p>>d;
Arr<int> a(n);
for(auto&i:a)cin>>i;
auto b=a;
reverse(b.begin(),b.end());
println(max(calc(a,p,d),calc(b,n-1-p,d)));
}
signed main(){
// int ti=0,t;cin>>t;
// while(++ti<=t)
// cout<<"Case #"<<ti<<": ",
solve();
}