Submission #36869

#	Time	Username	Problem	Language	Result	Execution time	Memory
36869		JustInCase	Bootfall (IZhO17_bootfall)	C++14	100 / 100	436 ms	5800 KiB

bootfall

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

const int MAX_N = 505;
const int MAX_SUM = 500 * 500 + 5;

int a[MAX_N], dp[MAX_SUM], aux[MAX_SUM], cntOkWith[MAX_SUM];

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

	int n;
	cin >> n;

	int sum = 0;
	dp[0] = 1;
	for(int i = 0; i < n; i++) {
		cin >> a[i];

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

		sum += a[i];
	}

	if(sum % 2 != 0 || dp[sum / 2] == 0) {
		cout << 0 << endl;
		return 0;
	}

	for(int i = 0; i < n; i++) {
		for(int j = 0; j <= sum; j++) {
			aux[j] = dp[j];
		}
		for(int j = a[i]; j <= sum; j++) {
			aux[j] -= aux[j - a[i]];
		}
		for(int j = 1; j <= sum; j++) {
			int newSum = sum - a[i] + j;
			if(newSum % 2 == 0 && aux[newSum / 2] != 0) {
				cntOkWith[j]++;
			}
		}
	}

	vector< int > ans;
	for(int i = 1; i <= sum; i++) {
		if(cntOkWith[i] == n) {
			ans.push_back(i);
		}
	}

	cout << ans.size() << endl;
	for(int x : ans) {
		cout << x << " ";
	}
	cout << endl;

	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