oj.uz

답안 #1089056

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1089056 2024-09-15T21:27:21 Z TAhmed33 Candies (JOI18_candies) C++
100 / 100
 472 ms 185684 KB 
#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();
}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 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

Subtask #2
92.0 / 92.0

# 결과 실행 시간 메모리 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