| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1138763 | t9unkubj | 휴가 (IOI14_holiday) | C++20 | 0 ms | 0 KiB |
#ifdef t9unkubj
#include"debug.cpp"
//#include"template_no_debug.h"
#else
#define dbg(...) 199958
#endif
#pragma GCC optimize("O3")
using namespace std;
#include<bits/stdc++.h>
using ll=long long;
using ull=unsigned long long;
template<class T>using vc=vector<T>;
template<class T>using vvc=vc<vc<T>>;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,j,n) for(ll i=(j);i<(ll)(n);i++)
#define DREP(i,n,m) for(ll i=(n);i>=(m);i--)
#define drep(i,n) for(ll i=((n)-1);i>=0;i--)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
template<class T,class F>
bool chmin(T &x, F y){
if(x>y){
x=y;
return true;
}
return false;
}
template<class T, class F>
bool chmax(T &x, F y){
if(x<y){
x=y;
return true;
}
return false;
}
double pass_time=0;
using S=pair<ll,ll>;
S e(){
return {0,0};
}
S op(S a,S b){
return S{a.first+b.first,a.second+b.second};
}
struct segtree{
int n;
vc<S>node;
segtree(int n_){
int N=1;
while((1<<N)<n_)N++;
n=1<<N;
node=vc<S>(n*2);
}
void set(int i,S x){
node[i+=n]=x;
while(i>>=1)node[i]=op(node[i*2],node[i*2+1]);
}
ll dive(int i,ll sm,int now,int k){
if(i>=2*n)return sm;
if(node[i].second+now<=k){
now+=node[i].second;
sm+=node[i].first;
return dive((i+1)*2,sm,now,k);
}
return dive(i*2,sm,now,k);
}
ll kth(int k){
if(node[1].second<=k)return node[1].first;
return dive(2,0,0,k);
}
};
ll brute(int n,int s,int d,vc<int>a){
ll Ans=0;
rep(t,2){
//往復しない
{
ll now_sum=0;
priority_queue<int,vc<int>,greater<>>que;
for(int i=s;i<n;i++){
que.push(a[i]);
now_sum+=a[i];
while(que.size()&&que.size()>d-(i-s)){
now_sum-=que.top();
que.pop();
}
chmax(Ans,now_sum);
}
}
//s>i>j
{
vc<int>idx(n);
iota(all(idx),0);
sort(all(idx),[&](int i,int j){
return a[i]>a[j];
});
vc<int>inv(n);
rep(i,n){
inv[idx[i]]=i;
}
rep(i,s){
segtree seg(n);
auto push=[&](int i){
seg.set(inv[i],{a[i],1});
};
auto erase=[&](int i){
seg.set(inv[i],e());
};
REP(k,i,s+1)push(k);
REP(j,s+1,n){
int W=s-i+j-i;
if(W>d)break;
push(j);
chmax(Ans,seg.kth(d-W));
}
}
}
s=n-1-s;
reverse(all(a));
}
return Ans;
}
ll solve(int n,int s,int d,vc<int>a){
ll Ans=0;
rep(t,2){
//往復しない
vc<int>idx(n);
iota(all(idx),0);
sort(all(idx),[&](int i,int j){
return a[i]>a[j];
});
vc<int>inv(n);
rep(i,n){
inv[idx[i]]=i;
}
{
ll now_sum=0;
priority_queue<ll,vc<ll>,greater<>>que;
for(int i=s;i<n;i++){
que.push(a[i]);
now_sum+=a[i];
while(que.size()&&(int)que.size()>d-(i-s)){
now_sum-=que.top();
que.pop();
}
chmax(Ans,now_sum);
}
}
//s>i>j
{
vc<ll>ans(n);
vc<int>best(n);
vc<int>used(n);
vc<array<int,5>>wait;
//(idx,best_l,best_r,l,r) best_l <= \argmax score[idx][j] best_r
wait.push_back({n/2,0,n-1,0,n-1}),used[n/2]=1;
while(wait.size()){
segtree seg(n);
auto push=[&](int i){
seg.set(inv[i],{a[i],1});
};
auto erase=[&](int i){
seg.set(inv[i],e());
};
sort(all(wait));
int sl=0,sr=-1;
for(auto&[i,tl,tr,l,r]:wait){
while(sr!=tl){
push(++sr);
}
while(sr<i){
if(sr>=tr)break;
push(++sr);
}
while(sl!=i){
erase(sl++);
}
while(1){
int W=(s-i)+(sr-i);
if(W>d)break;
if(chmax(ans[i],seg.kth(d-W))){
best[i]=sr;
}
if(sr==tr)break;
push(++sr);
}
}
decltype(wait) nxt;
auto make=[&](int x,int tl,int tr,int l,int r){
if(x<n&&!used[x]){
used[x]=1;
nxt.push_back({x,tl,tr,l,r});
}
};
for(auto&[x,tl,tr,l,r]:wait){
make((l+x)/2,tl,best[x],l,x);
make((r+x)/2,best[x],tr,x,r);
}
wait=move(nxt);
}
chmax(Ans,*max_element(all(ans)));
}
s=n-1-s;
reverse(all(a));
}
return Ans;
}
void input(){
int n,s,d;
cin>>n>>s>>d;
vc<int>a(n);
rep(i,n)cin>>a[i];
dbg(solve(n,s,d,a));
}
void run(){
mt19937 mt;
while(1){
int n=5,s=mt()%n,d=mt()%(n*2);
vc<int>a(n);
rep(i,n)a[i]=mt()%(n*2);
if(solve(n,s,d,a)!=brute(n,s,d,a)){
dbg(n,s,d,a);
dbg(solve(n,s,d,a));
dbg(brute(n,s,d,a));
assert(0);
}
}
}
/*
signed main(){
#ifdef t9unkubj
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
input();
}*/