Submission #1089056

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089056		TAhmed33	Candies (JOI18_candies)	C++98	100 / 100	472 ms	185684 KiB

candies

#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 / 8
• Subtask 2: 92 / 92