Submission #36869

#TimeUsernameProblemLanguageResultExecution timeMemory
36869JustInCaseBootfall (IZhO17_bootfall)C++14
100 / 100
436 ms5800 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...