| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1036722 | trandangquang | Holiday (IOI14_holiday) | C++14 | 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 <bits/stdc++.h>
using namespace std;
#define task "test"
#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for(int i = (a); i >= (b); --i)
#define sz(a) (int)(a).size()
#define all(a) (a).begin(), (a).end()
#define bit(s, i) (((s) >> (i)) & 1)
#define ii pair <int, int>
#define vii vector <ii>
#define vi vector <int>
#define fi first
#define se second
#define int long long
#define ll long long
#define eb emplace_back
#define pb push_back
#define __builtin_popcount __builtin_popcountll
void solve();
int32_t main() {
if(fopen(task".inp", "r")) {
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
// cin.tie(0)->sync_with_stdio(0);
int tc = 1; // cin >> tc;
FOR(i, 1, tc) {
solve();
}
}
const int N = 250005;
int n, st, d, att[N], upto[20]; ii bestr[N], bestl[N];
vi rar;
/// bestr[u] = {gia tri, vi tri gan nhat} khi di voi thoi gian u
/// bestl[u]: tuong tu voi bestr[u]
struct segmentTree {
struct node {
int num = 0;
ll sum = 0;
} st[N<<2];
void reset() {
node tmp = {0, 0};
fill(begin(st), end(st), tmp);
}
void upd(int x, int val) {
int id=1, l=1, r=sz(rar);
while(1) {
if(l==r) break;
int m=(l+r)>>1;
if(x<=m) {
id = id<<1;
r=m;
}
else {
id = id<<1|1;
l=m+1;
}
}
st[id].num += val;
st[id].sum += val*rar[x-1];
while(id>1) {
id /= 2;
st[id].num = st[id<<1].num + st[id<<1|1].num;
st[id].sum = st[id<<1].sum + st[id<<1|1].sum;
}
}
ll get_max(int nli) {
int id=1, l=1, r=sz(rar);
ll res = 0;
while(l<=r) {
if(l==r) break;
int m=(l+r)>>1;
if(st[id<<1|1].num <= nli) {
nli-=st[id<<1|1].num;
res+=st[id<<1|1].sum;
id=id<<1;
r=m;
}
else {
id=id<<1|1;
l=m+1;
}
}
return res + min(nli, st[id].num)*rar[l-1];
}
} smt[20];
void calcr(int L, int R, int optL, int optR, int lvl) {
// printf("Range: %d %d, optRange: %d %d\n", L, R, optL, optR);
if(L > R) return;
int mid = (L+R) >> 1;
FOR(i, optL, optR) {
if(mid-(i-st) < 0) break; /// neu nhu di qua xa -> break
while(upto[lvl] < i) smt[lvl].upd(att[++upto[lvl]], 1);
int nwVal = smt[lvl].get_max(mid-(i-st));
if(nwVal > bestr[mid].fi) {
bestr[mid].fi = nwVal;
bestr[mid].se = i;
}
}
calcr(L, mid-1, optL, bestr[mid].se, lvl+1);
calcr(mid+1, R, bestr[mid].se, optR, lvl+1);
}
void calcl(int L, int R, int optL, int optR, int lvl) {
// printf("Range: %d %d, optRange: %d %d\n", L, R, optL, optR);
if(L > R) return;
int mid = (L+R) >> 1;
FORD(i, optR, optL) {
if(mid-(st-i) < 0) break; ///
while(upto[lvl] > i) smt[lvl].upd(att[--upto[lvl]], 1);
int nwVal = smt[lvl].get_max(mid-(st-i));
// if(mid == 3) cout << i << " " << nwVal << " " << mid-(st-i) << '\n';
if(nwVal > bestl[mid].fi) {
bestl[mid].fi = nwVal;
bestl[mid].se = i;
}
}
// cout << mid << " " << bestl[mid].se<<" "<<bestl[mid].fi<<'\n';
calcl(L, mid-1, bestl[mid].se, optR, lvl+1);
calcl(mid+1, R, optL, bestl[mid].se, lvl+1);
}
void solve() {
cin >> n >> st >> d;
++st;
FOR(i, 1, n) {
cin >> att[i];
rar.eb(att[i]);
}
sort(all(rar));
FOR(i, 1, n) {
att[i] = upper_bound(all(rar), att[i]) - rar.begin();
}
memset(bestr, -1, sizeof(bestr));
memset(bestl, -1, sizeof(bestl));
FOR(i, 1, 19) upto[i] = st;
calcr(1, d, st+1, n, 1);
FOR(i, 1, 19) {
smt[i].reset();
upto[i] = st;
}
calcl(1, d, 1, st-1, 1);
// cout << "left things:\n";
// FOR(i, 1, d) printf("time: %d, pos: %d, val: %d\n", i, bestl[i].se, bestl[i].fi);
int ans = 0;
bestl[0].fi = bestr[0].fi = 0;
FOR(i, 0, d) {
if(d-i-(bestr[i].se-st)>=0) {
ans = max(ans, bestr[i].fi + bestl[d-i-(bestr[i].se-st)].fi);
}
if(d-i-(st-bestl[i].se)>=0) {
ans = max(ans, bestl[i].fi + bestr[d-i-(st-bestl[i].se)].fi);
}
ans = max(ans, bestl[i].fi);
ans = max(ans, bestr[i].fi);
}
// cout<<bestr[2].fi<<" "<<d-2-(bestr[2].se-st)<<'\n';
// cout<<bestl[3].fi << '\n';
--d;
FOR(i, 0, d) {
if(d-i-(bestr[i].se-st)>=0) {
ans = max(ans, bestr[i].fi + bestl[d-i-(bestr[i].se-st)].fi + rar[att[st] - 1]);
// if(i==2) cout<<att[st]<<'\n';
}
if(d-i-(st-bestl[i].se)>=0) {
ans = max(ans, bestl[i].fi + bestr[d-i-(st-bestl[i].se)].fi + rar[att[st] - 1]);
}
ans = max(ans, bestl[i].fi + rar[att[st] - 1]);
ans = max(ans, bestr[i].fi + rar[att[st] - 1]);
}
cout << ans;
}