Submission #486587

#	Time	Username	Problem	Language	Result	Execution time	Memory
486587		ez_ioi	Candies (JOI18_candies)	C++17	0 / 100	5055 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];
bool used[mxN];
ll dp[mxN], p[mxN], res[mxN];

int main() {
	ios :: sync_with_stdio(false), cin.tie(nullptr);
	cin >> n;
	for (int i = 1; i <= n; ++i) cin >> a[i];
	dp[1] = a[1];
	for (int i = 2; i <= n; ++i) {
		if (dp[i - 1] >= dp[i - 2] + a[i]) {
			dp[i] = dp[i - 1];
			if (used[i - 1]) p[i] = i - 1;
			else p[i] = p[i - 1];
		}
		else {
			dp[i] = dp[i - 2] + a[i]; used[i] = 1;
			if (used[i - 2]) p[i] = i - 2;
			else p[i] = p[i - 2];
		}
	}
	int now = n;
	if (!used[now]) now = p[now];
	multiset <int> lmao;
	ll ans = 0; 
	while (now) {
		ans += a[now];
		lmao.insert(a[now]);
		now = p[now];
	}
	if (n & 1) {
		if (lmao.size() < (n + 1) / 2) {
			ll bruh = 0;
			for (int i = 1; i <= n; i += 2) bruh += a[i];
			res[(n + 1) / 2] = bruh;
		}
	}
	for (int i = n / 2; i > 0; i--) {
		res[i] = ans;
		ans -= *lmao.begin();
		lmao.erase(lmao.begin());
	}
	for (int i = 1; i <= (n + 1) / 2; ++i) cout << res[i] << '\n';
	return 0;
}

Compilation message (stderr)

candies.cpp: In function 'int main()':
candies.cpp:39:19: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   39 |   if (lmao.size() < (n + 1) / 2) {
      |       ~~~~~~~~~~~~^~~~~~~~~~~~~

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