| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 884878 |
2023-12-08T15:27:56 Z |
tade |
Holiday (IOI14_holiday) |
C++17 |
|
699 ms |
60752 KB |
#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;
}
} T;
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];
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);
}
int run() {
T.reset();
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]);
}
return ans;
}
int findMaxAttraction(int32_t _n, int32_t _start, int32_t _d, int32_t _a[]) {
n = _n;
start = _start + 1;
d = _d;
for(int i = 1; i <= n; ++ i) a[i] = _a[i - 1];
return run();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4952 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2908 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4956 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2908 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2908 KB |
Output is correct |
| 6 |
Correct |
1 ms |
2908 KB |
Output is correct |
| 7 |
Correct |
1 ms |
2908 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
289 ms |
6736 KB |
Output is correct |
| 2 |
Correct |
234 ms |
6936 KB |
Output is correct |
| 3 |
Correct |
314 ms |
6736 KB |
Output is correct |
| 4 |
Correct |
233 ms |
6740 KB |
Output is correct |
| 5 |
Correct |
268 ms |
5684 KB |
Output is correct |
| 6 |
Correct |
86 ms |
6044 KB |
Output is correct |
| 7 |
Correct |
146 ms |
4584 KB |
Output is correct |
| 8 |
Correct |
179 ms |
5100 KB |
Output is correct |
| 9 |
Correct |
76 ms |
6944 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
7768 KB |
Output is correct |
| 2 |
Correct |
7 ms |
4956 KB |
Output is correct |
| 3 |
Correct |
11 ms |
7752 KB |
Output is correct |
| 4 |
Correct |
12 ms |
5724 KB |
Output is correct |
| 5 |
Correct |
11 ms |
5468 KB |
Output is correct |
| 6 |
Correct |
4 ms |
3676 KB |
Output is correct |
| 7 |
Correct |
3 ms |
2908 KB |
Output is correct |
| 8 |
Correct |
3 ms |
2876 KB |
Output is correct |
| 9 |
Correct |
3 ms |
2904 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
286 ms |
11192 KB |
Output is correct |
| 2 |
Correct |
699 ms |
60752 KB |
Output is correct |
| 3 |
Correct |
317 ms |
31472 KB |
Output is correct |
| 4 |
Correct |
11 ms |
4956 KB |
Output is correct |
| 5 |
Correct |
3 ms |
3024 KB |
Output is correct |
| 6 |
Correct |
4 ms |
2908 KB |
Output is correct |
| 7 |
Correct |
3 ms |
2908 KB |
Output is correct |
| 8 |
Correct |
582 ms |
30292 KB |
Output is correct |
| 9 |
Correct |
597 ms |
30152 KB |
Output is correct |
