| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1036499 | phong | 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.
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#define ll long long
#define int long long
const int nmax = 3e5 + 5, N = 1e5;
const ll oo = 1e18;
const int lg = 19, M = 2, mod = 1e6;
#define pii pair<ll, ll>
#define fi first
#define se second
#define debug(a, n) for(int i = 1; i <= n; ++i) cout << a[i] << ' '; cout << "\n";
#define endl "\n"
#define task "code"
using namespace std;
int n, st, D;
pii a[nmax];
int rev[nmax], b[nmax];
int best[nmax][2];
ll dp[nmax][2];
pii tree[nmax << 2];
void build(int id, int l, int r){
tree[id].fi = 0;
tree[id].se = 0;
if(l != r){
int mid = r + l >> 1;
build(id << 1, l, mid);
build(id << 1| 1, mid + 1, r);
}
}
void update(int id, int l, int r, int u, int val){
if(l > u || r < u) return;
if(l == r){
tree[id] = {val, 1};
return;
}
int mid = r + l >> 1;
update(id << 1, l, mid, u, val);
update(id << 1 | 1, mid + 1, r, u, val);
tree[id].fi = tree[id << 1].fi + tree[id << 1 | 1].fi;
tree[id].se = tree[id << 1].se + tree[id << 1 | 1].se;
}
ll get(int id, int l, int r, int k){
if(tree[id].se <= k) return tree[id].fi;
int mid = r+ l >> 1;
if(tree[id << 1 | 1].se >= k) return get(id << 1 | 1, mid + 1, r, k);
return tree[id << 1 | 1].fi + get(id << 1, l ,mid, k - tree[id << 1 | 1].se);
}
int idx[nmax];
struct node{
int L, R, from, to;
};
vector<node> adj[21];
void Init(int ok){
if(st > n) return;
for(int i = 1; i <= n; ++i) rev[a[i].se] = i;
for(int e = 1; e <= 20; ++e)adj[e].clear();
adj[1].push_back({1, D, st, n});
for(int e = 1; e <= 20; ++e){
if(adj[e].empty()) continue;
build(1, 1, n);
int pos = st;
for(auto [L, R, from, to] : adj[e]){
int mid = R + L >> 1;
auto &FF = best[mid][ok];
FF = 1e9;
ll &ma = dp[mid][ok];
ma = -1;
// cout << from << ' ' << to << ' ';
for(int i = from; i <= to; ++i){
if(mid - (i - st) >= 0){
while(pos <= i){
int x = rev[pos];
update(1, 1, n, x, a[x].fi);
++pos;
}
ll cur = get(1, 1, n, mid - (i - st));
// cout << mid << ' ' << i - st << ' ' << mid - (i - st) << ' ' << cur << endl;
if(ma < cur){
ma = cur;
FF = i;
}
}
}
// if(!ddd) cout << "?";
if(L < mid) adj[e + 1].push_back({L, mid - 1, from, FF});
if(mid < R) adj[e + 1].push_back({mid + 1, R, FF, to});
}
// cout << endl;
}
for(int i = 1; i <= D; ++i) best[i][ok] -= st;
}
main(){
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen(task".inp", "r", stdin);
// freopen(task".ans", "w", stdout);
cin >> n >> st >> D;
++st;
for(int i = 1; i <= n; ++i) cin >> a[i].fi, a[i].se = i;
sort(a + 1,a + 1 + n,[](pii a, pii b){
return a.fi < b.fi;
});
Init(0);
st = n - st + 2;
for(int i = 1; i <= D; ++i) a[i].se = n - a[i].se + 1;
Init(1);
st = n - st + 2;
// for(int i = 1; i <= D; ++i) cout << dp[i][1] << ' ';
ll ans = 0;
for(int x = 0; x <= D; ++x){
ll val = dp[x][0];
int y = D - (best[x][0] * 2) - 1;
if(y >= 0) val += dp[y][1];
ans = max(ans, val);
}
cout << ans;
}
/*
5 2 7
10 2 20 30 1
from to
*/