#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("Ofast")
typedef long long ll;
#define mid ((l + r) >> 1)
#define tl (node + 1)
#define tr (node + 2 * (mid - l + 1))
const int MAXN = 2e5 + 25;
ll a[MAXN], n;
vector <ll> tree[MAXN << 2][2][2];
vector <ll> merge (vector <ll> x, vector <ll> y) {
vector <ll> ret((int)x.size() + (int)y.size() - 1, 0);
int g = 0, h = 0;
ret[0] = x[0] + y[0];
while (g + 1 < (int)x.size() && h + 1 < (int)y.size()) {
if (x[g + 1] + y[h] > x[g] + y[h + 1]) {
g++;
} else {
h++;
}
ret[g + h] = x[g] + y[h];
}
while (g + 1 < (int)x.size()) {
g++; ret[g + h] = x[g] + y[h];
}
while (h + 1 < (int)y.size()) {
h++; ret[g + h] = x[g] + y[h];
}
return ret;
}
vector <ll> mx (vector <ll> x, vector <ll> y) {
vector <ll> ret(max(x.size(), y.size()), 0);
for (int i = 0; i < (int)x.size(); i++) {
ret[i] = max(ret[i], x[i]);
}
for (int i = 0; i < (int)y.size(); i++) {
ret[i] = max(ret[i], y[i]);
}
return ret;
}
void recurse (int l, int r, int node) {
if (l == r) {
tree[node][0][0] = {0};
tree[node][0][1] = {0};
tree[node][1][0] = {0};
tree[node][1][1] = {0, a[l]};
return;
}
recurse(l, mid, tl);
recurse(mid + 1, r, tr);
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
auto g = merge(tree[tl][i][0], tree[tr][0][j]);
auto h = merge(tree[tl][i][1], tree[tr][0][j]);
auto k = merge(tree[tl][i][0], tree[tr][1][j]);
tree[node][i][j] = mx(g, h);
tree[node][i][j] = mx(tree[node][i][j], k);
}
}
}
void solve () {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
recurse(1, n, 1);
for (int i = 1; i <= (n + 1) / 2; i++) {
ll mx = 0;
for (int j = 0; j < 2; j++) {
for (int k = 0; k < 2; k++) {
if ((int)tree[1][j][k].size() > i) {
mx = max(mx, tree[1][j][k][i]);
}
}
}
cout << mx << '\n';
}
}
signed main () {
ios::sync_with_stdio(0); cin.tie(0);
int tc = 1; //cin >> tc;
while (tc--) solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
76368 KB |
Output is correct |
| 2 |
Correct |
38 ms |
76376 KB |
Output is correct |
| 3 |
Correct |
31 ms |
76376 KB |
Output is correct |
| 4 |
Correct |
29 ms |
76372 KB |
Output is correct |
| 5 |
Correct |
31 ms |
76380 KB |
Output is correct |
| 6 |
Correct |
36 ms |
76372 KB |
Output is correct |
| 7 |
Correct |
34 ms |
76368 KB |
Output is correct |
| 8 |
Correct |
50 ms |
76368 KB |
Output is correct |
| 9 |
Correct |
47 ms |
76332 KB |
Output is correct |
| 10 |
Correct |
33 ms |
76368 KB |
Output is correct |
| 11 |
Correct |
50 ms |
76488 KB |
Output is correct |
| 12 |
Correct |
34 ms |
76372 KB |
Output is correct |
| 13 |
Correct |
33 ms |
76372 KB |
Output is correct |
| 14 |
Correct |
33 ms |
76460 KB |
Output is correct |
| 15 |
Correct |
33 ms |
76416 KB |
Output is correct |
| 16 |
Correct |
37 ms |
76652 KB |
Output is correct |
| 17 |
Correct |
34 ms |
76320 KB |
Output is correct |
| 18 |
Correct |
33 ms |
76424 KB |
Output is correct |
| 19 |
Correct |
33 ms |
76368 KB |
Output is correct |
| 20 |
Correct |
37 ms |
76472 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
76368 KB |
Output is correct |
| 2 |
Correct |
38 ms |
76376 KB |
Output is correct |
| 3 |
Correct |
31 ms |
76376 KB |
Output is correct |
| 4 |
Correct |
29 ms |
76372 KB |
Output is correct |
| 5 |
Correct |
31 ms |
76380 KB |
Output is correct |
| 6 |
Correct |
36 ms |
76372 KB |
Output is correct |
| 7 |
Correct |
34 ms |
76368 KB |
Output is correct |
| 8 |
Correct |
50 ms |
76368 KB |
Output is correct |
| 9 |
Correct |
47 ms |
76332 KB |
Output is correct |
| 10 |
Correct |
33 ms |
76368 KB |
Output is correct |
| 11 |
Correct |
50 ms |
76488 KB |
Output is correct |
| 12 |
Correct |
34 ms |
76372 KB |
Output is correct |
| 13 |
Correct |
33 ms |
76372 KB |
Output is correct |
| 14 |
Correct |
33 ms |
76460 KB |
Output is correct |
| 15 |
Correct |
33 ms |
76416 KB |
Output is correct |
| 16 |
Correct |
37 ms |
76652 KB |
Output is correct |
| 17 |
Correct |
34 ms |
76320 KB |
Output is correct |
| 18 |
Correct |
33 ms |
76424 KB |
Output is correct |
| 19 |
Correct |
33 ms |
76368 KB |
Output is correct |
| 20 |
Correct |
37 ms |
76472 KB |
Output is correct |
| 21 |
Correct |
472 ms |
182880 KB |
Output is correct |
| 22 |
Correct |
462 ms |
182940 KB |
Output is correct |
| 23 |
Correct |
456 ms |
182816 KB |
Output is correct |
| 24 |
Correct |
431 ms |
182568 KB |
Output is correct |
| 25 |
Correct |
415 ms |
182672 KB |
Output is correct |
| 26 |
Correct |
410 ms |
182556 KB |
Output is correct |
| 27 |
Correct |
405 ms |
182800 KB |
Output is correct |
| 28 |
Correct |
406 ms |
182820 KB |
Output is correct |
| 29 |
Correct |
400 ms |
182824 KB |
Output is correct |
| 30 |
Correct |
411 ms |
182768 KB |
Output is correct |
| 31 |
Correct |
415 ms |
182928 KB |
Output is correct |
| 32 |
Correct |
399 ms |
182740 KB |
Output is correct |
| 33 |
Correct |
408 ms |
182568 KB |
Output is correct |
| 34 |
Correct |
405 ms |
182564 KB |
Output is correct |
| 35 |
Correct |
433 ms |
182728 KB |
Output is correct |
| 36 |
Correct |
441 ms |
185616 KB |
Output is correct |
| 37 |
Correct |
411 ms |
185576 KB |
Output is correct |
| 38 |
Correct |
431 ms |
185580 KB |
Output is correct |
| 39 |
Correct |
397 ms |
185528 KB |
Output is correct |
| 40 |
Correct |
403 ms |
185460 KB |
Output is correct |
| 41 |
Correct |
403 ms |
185268 KB |
Output is correct |
| 42 |
Correct |
414 ms |
185620 KB |
Output is correct |
| 43 |
Correct |
417 ms |
185496 KB |
Output is correct |
| 44 |
Correct |
444 ms |
185624 KB |
Output is correct |
| 45 |
Correct |
397 ms |
185612 KB |
Output is correct |
| 46 |
Correct |
399 ms |
185488 KB |
Output is correct |
| 47 |
Correct |
403 ms |
185684 KB |
Output is correct |
| 48 |
Correct |
418 ms |
185384 KB |
Output is correct |
| 49 |
Correct |
409 ms |
185368 KB |
Output is correct |
| 50 |
Correct |
415 ms |
185364 KB |
Output is correct |
