Submission #759748

#	Time	Username	Problem	Language	Result	Execution time	Memory
759748		NK_	Bootfall (IZhO17_bootfall)	C++17	100 / 100	42 ms	2652 KiB

bootfall

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'

const int nax = 505;
const int kax = nax * nax;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N; cin >> N;
	vector<int> A(N); for(auto& x : A) cin >> x;

	bitset<kax> ans; ans.set();

	function<void(int, int, bitset<kax>&)> dnc = [&](int l, int r, bitset<kax>& dp) {
		// cout << l << " " << r << endl;
		int m = (l + r) / 2;

		if (l > r) return;

		if (l == r) {
			dp <<= A[l];
			ans &= dp;
			return;
		}

		bitset<kax> ndp;
		// GO LEFT
		ndp = dp;
		for(int x = m + 1; x <= r; x++) ndp |= (ndp << 2*A[x]);
		dnc(l, m, ndp);

		// GO RIGHT
		ndp = dp;
		for(int x = l; x <= m; x++) ndp |= (ndp << 2*A[x]);
		dnc(m+1, r, ndp);
	};

	int S = accumulate(begin(A), end(A), 0);

	if (S % 2) {
		cout << 0 << nl;
		return 0;
	}

	bitset<kax> dp; dp[0] = 1;
	for(auto x : A) dp |= (dp << x);

	if (!dp[S / 2]) {
		cout << 0 << nl;
		return 0;
	}

	dp.reset(); dp[0] = 1;
	dnc(0, N - 1, dp);

	vector<int> ANS;
	for(int SUM = 0; SUM <= S; SUM++) if (ans[SUM]) ANS.push_back(S - SUM);
	reverse(begin(ANS), end(ANS));

	cout << size(ANS) << nl;
	for(auto x : ANS) cout << x << " ";
	cout << nl;

    return 0;
}

• Subtask 1: 6 / 6
• Subtask 2: 7 / 7
• Subtask 3: 15 / 15
• Subtask 4: 16 / 16
• Subtask 5: 21 / 21
• Subtask 6: 35 / 35