Submission #851696

#	Time	Username	Problem	Language	Result	Execution time	Memory
851696		stdfloat	Bootfall (IZhO17_bootfall)	C++17	100 / 100	265 ms	5828 KiB

bootfall

#include <bits/stdc++.h>
using namespace std;

#define int long long

int32_t main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);

	int n;
	cin >> n;

	int sm = 0;
	vector<int> a(n + 1);
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		sm += a[i];
	}

	vector<int> dp(sm + 1, 0); dp[0] = 1;
	for (int i = 1; i <= n; i++) {
		for (int j = sm - a[i]; j >= 0; j--) {
			dp[j + a[i]] += dp[j];
		}
	}
	if ((sm & 1) || !dp[(sm>>1)]) {
		return cout << 0, 0;
	}

	vector<int> cnt(sm + 1, 0);
	for (int i = 1; i <= n; i++) {
		int x = sm - a[i];
		for (int j = 0; j <= sm - a[i]; j++) {
			dp[j + a[i]] -= dp[j];
		}

		for (int j = ((x + 1)>>1); j <= x; j++) {
			cnt[(j<<1) - x] += !!dp[j];
		}

		for (int j = sm - a[i]; j >= 0; j--) {
			dp[j + a[i]] += dp[j];
		}
	}

	vector<int> v;
	for (int i = 0; i <= sm; i++) {
		if (cnt[i] == n) v.push_back(i);
	}

	cout << (int)v.size() << "\n";
	for (auto i : v) {
		cout << i << ' ';
	}
}

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