Submission #1310246

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310246		mat_jur	Candies (JOI18_candies)	C++20	100 / 100	381 ms	13284 KiB

candies

#include "bits/stdc++.h"
using namespace std;
#ifdef DEBUG
auto&operator<<(auto &o, pair<auto, auto> p) {o << "(" << p.first << ", " << p.second << ")"; return o;}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{"; for(auto e : x) o<<e<<", "; return o<<"}";}
#define debug(X) cerr << "["#X"]: " << X << '\n';
#else 
#define cerr if(0)cout
#define debug(X) ;
#endif
using ll = long long;
#define all(v) (v).begin(), (v).end()
#define ssize(x) int(x.size())
#define fi first
#define se second
#define mp make_pair
#define eb emplace_back

struct DP {
	vector<ll> t[2][2];

	DP() {
		t[0][0] = t[0][1] = t[1][0] = t[1][1] = vector<ll>{0LL};
	}
};

vector<ll> max(vector<ll> a, const vector<ll> &b) {
	for (int i = 0; i < ssize(b); ++i) {
		if (i >= ssize(a)) a.eb(0);
		a[i] = max(a[i], b[i]);
	}
	return a;
}

vector<ll> comb(const vector<ll> &a, const vector<ll> &b) {
	vector<ll> res;

	int i = 0, j = 0;
	while (i < ssize(a) && j < ssize(b)) {
		res.eb(a[i] + b[j]);
		if (i == ssize(a) - 1)
			++j;
		else if (j == ssize(b) - 1)
			++i;
		else if (a[i+1] - a[i] > b[j+1] - b[j]) 
			++i;
		else 
			++j;
	}

	return res;
}

DP comb(const DP &a, const DP &b) {
	DP ret;
	for (int i = 0; i < 2; ++i) {
		for (int j = 0; j < 2; ++j) {
			ret.t[i][j] = max(ret.t[i][j], comb(a.t[i][0], b.t[0][j]));
			ret.t[i][j] = max(ret.t[i][j], comb(a.t[i][0], b.t[1][j]));
			ret.t[i][j] = max(ret.t[i][j], comb(a.t[i][1], b.t[0][j]));
		}
	}

	return ret;
}

DP solve(int l, int r, const vector<int> &a) {
	if (l == r) {
		DP res;
		res.t[1][1].eb(a[l]);
		return res;
	}

	int mid = (l + r) / 2;

	DP dp_l = solve(l, mid, a), dp_r = solve(mid+1, r, a);

	return comb(dp_l, dp_r);
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr);

	int n;
	cin >> n;
	vector<int> a(n);
	for (int &x : a) cin >> x;

	DP dp = solve(0, n-1, a);

	for (int i = 1; i <= (n+1)/2; ++i) {
		ll res = 0;
		if (i < ssize(dp.t[0][0])) res = max(res, dp.t[0][0][i]);
		if (i < ssize(dp.t[0][1])) res = max(res, dp.t[0][1][i]);
		if (i < ssize(dp.t[1][0])) res = max(res, dp.t[1][0][i]);
		if (i < ssize(dp.t[1][1])) res = max(res, dp.t[1][1][i]);
		cout << res << '\n';
	}

	return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 92 / 92