| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 884873 | tade | 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 <bits/stdc++.h>
using namespace std;
int log2_floor(unsigned long long i) {
return i ? __builtin_clzll(1) - __builtin_clzll(i) : -1;
}
#define int long long
// #define ll long long
#define ld long double
#define all(x) x.begin(), x.end()
template<typename T>
bool minimise(T &lhs, T rhs) {
if(lhs > rhs) { lhs = rhs; return true; }
return false;
}
template<typename T>
bool maximise(T &lhs, T rhs) {
if(lhs < rhs) { lhs = rhs; return true; }
return false;
}
const int nmax = 1e5;
const int LOG = 29;
struct trie {
struct node {
int sum, cnt;
node *child[2];
node() {
sum = cnt = 0;
child[0] = child[1] = NULL;
}
};
node *root = new node();
void reset() {
// fugg the redundant memory's gonna be insane
root = new node();
}
void add(int x) {
node *p = root;
++ p->cnt;
p->sum += x;
for(int i = LOG; i >= 0; -- i) {
int nxt = x >> i & 1;
if(p->child[nxt] == NULL) p->child[nxt] = new node();
p = p->child[nxt];
++ p->cnt;
p->sum += x;
}
}
bool exist(int x) {
node *p = root;
for(int i = LOG; i >= 0; -- i) {
int nxt = x >> i & 1;
if(p->child[nxt] == NULL) return false;
p = p->child[nxt];
}
return true;
}
void del(int x) {
if(!exist(x)) return;
node *p = root;
-- p->cnt;
p->sum -= x;
for(int i = LOG; i >= 0; -- i) {
int nxt = x >> i & 1;
p = p->child[nxt];
-- p->cnt;
p->sum -= x;
}
}
// sum of k largest numbers
int get(int k) {
if(root->cnt <= k) return root->sum;
node *p = root;
int ans = 0, mask = 0;
for(int i = LOG; i >= 0; -- i) {
int j = 1;
for(; j >= 0; -- j) {
if(p->child[j] == NULL) continue;
if(k > p->child[j]->cnt) {
k -= p->child[j]->cnt;
ans += p->child[j]->sum;
}
else break;
}
p = p->child[j];
mask |= (j << i);
}
return ans + k * mask;
}
};
int n, start, d;
int a[nmax + 5];
int f[3 * nmax + 5], optf[3 * nmax + 5], g[3 * nmax + 5], optg[3 * nmax + 5];
trie T;
void dnc(int *dp, int *opt, int l, int r, int optl, int optr) {
if(l > r || optl > optr) return;
// cerr << l << " " << r << " " << optl << " " << optr << "\n";
if(optl == optr) {
for(int i = l; i <= r; ++ i) {
opt[i] = optl;
dp[i] = T.get(i - (optl - start));
}
return;
}
int mid = (l + r) >> 1;
// cerr << " " << mid << "\n";
for(int i = optr; i >= optl; -- i) {
// cerr << " " << i << " " << mid - (i - start) << "\n";
int mx = T.get(mid - (i - start));
if(mx >= dp[mid]) {
dp[mid] = mx;
opt[mid] = i;
}
// cerr << " " << i << " " << mid - (i - start) << " " << mx << " " << opt[mid] << " " << dp[mid] << "\n";
T.del(a[i]);
}
// cerr << " " << "opt done\n";
for(int i = optl; i <= opt[mid]; ++ i) T.add(a[i]);
dnc(dp, opt, l, mid - 1, optl, opt[mid]);
for(int i = opt[mid] + 1; i <= optr; ++ i) T.add(a[i]);
dnc(dp, opt, mid + 1, r, opt[mid], optr);
}
int32_t main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n >> start >> d;
++ start;
for(int i = 1; i <= n; ++ i) cin >> a[i];
for(int i = start; i <= n; ++ i) T.add(a[i]);
dnc(f, optf, 1, d, start, n);
// for(int i = 1; i <= d; ++ i) cerr << f[i] << " ";
// cerr << "\n";
// for(int i = 1; i <= d; ++ i) cerr << optf[i] << " ";
// cerr << "\n";
reverse(a + 1, a + 1 + n);
start = n + 1 - start;
T.reset();
for(int i = start + 1; i <= n; ++ i) T.add(a[i]);
dnc(g, optg, 1, d, start + 1, n);
for(int i = 1; i <= d; ++ i) optg[i] = n + 1 - optg[i];
// for(int i = 1; i <= d; ++ i) cerr << g[i] << " ";
// cerr << "\n";
// for(int i = 1; i <= d; ++ i) cerr << optg[i] << " ";
// cerr << "\n";
start = n + 1 - start;
int ans = 0;
for(int i = 1; i <= d; ++ i) {
maximise(ans, max(f[i], g[i]));
int vis_cnt = d - i - (optf[i] - start);
if(vis_cnt >= 0) maximise(ans, f[i] + g[vis_cnt]);
vis_cnt = d - i - (start - optg[i]);
if(vis_cnt >= 0) maximise(ans, g[i] + f[vis_cnt]);
}
cout << ans;
}