Submission #486597

#	Time	Username	Problem	Language	Result	Execution time	Memory
486597		ez_ioi	Candies (JOI18_candies)	C++17	0 / 100	5016 ms	332 KiB

candies

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int mxN = 2e5 + 5, mod = 1e9 + 7, LOG = 20;

int n, a[mxN];
ll p[mxN], res[mxN];
pair <ll, int> dp[mxN];

void solve(int l, int r) {
	vector <int> arr;
	arr.push_back(0);
	for (int i = l; i <= r; ++i) arr.push_back(a[i]);
	int m = (r - l + 1);
	dp[1] = {a[1], 1ll};
	for (int i = 2; i <= m; ++i) {
		if (dp[i - 1].first >= dp[i - 2].first + arr[i]) {
			p[i] = dp[i - 1].second;
			dp[i] = dp[i - 1];
		}
		else {
			p[i] = dp[i - 2].second;
			dp[i] = {dp[i - 2].first + arr[i], i}; 
		}
	}
	int now = dp[m].second;
	multiset <int> lmao;
	ll ans = 0; 
	while (now) {
		ans += arr[now];
		lmao.insert(arr[now]);
		now = p[now];
	}
	if (m & 1) {
		if ((int)lmao.size() < (m + 1) / 2) {
			ll bruh = 0;
			for (int i = 1; i <= m; i += 2) bruh += arr[i];
			res[(m + 1) / 2] = max(res[(m + 1) / 2], bruh);
			for (int i = m / 2; i > 0; i--) {
				res[i] = max(res[i], ans);
				ans -= *lmao.begin();
				lmao.erase(lmao.begin());
			}		
			return;
		}
	}
	for (int i = (m + 1) / 2; i > 0; i--) {
		res[i] = max(res[i], ans);
		ans -= *lmao.begin();
		lmao.erase(lmao.begin());
	}
	return;
}

int main() {
	ios :: sync_with_stdio(false), cin.tie(nullptr);
	cin >> n;
	for (int i = 1; i <= n; ++i) cin >> a[i];
	solve(1, n);
	if (n != 1) solve(2, n), solve(1, n - 1);
	for (int i = 1; i <= (n + 1) / 2; ++i) cout << res[i] << '\n';
	return 0;
}

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