제출 #867300

#제출 시각아이디문제언어결과실행 시간메모리
867300Halym2007Bootfall (IZhO17_bootfall)C++11
100 / 100
334 ms3528 KiB
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 5e2 + 5;
const int NN = N * N;
#define pb push_back
#define sz size()
#define ff first
#define ss second
int sum, n, dp[NN], san[NN], a[N];
vector <int> jog;
int main () {
//	freopen("input.txt", "r", stdin);
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
		sum += a[i];
	}
	dp[0] = 1;
	for (int i = 1; i <= n; ++i) {
		for (int j = sum - a[i]; j >= 0; j--) {
			if (dp[j]) {
				dp[j + a[i]] += dp[j];
			}
		}
	}
	if (sum % 2 == 1 or !dp[sum / 2]) return cout << "0", 0;
	for (int i = 1; i <= n; ++i) {
		for (int j = a[i]; j <= sum; ++j) {
			dp[j] -= dp[j - a[i]];
		}
		for (int j = 0; j <= sum; ++j) {
			// optimization etmeli
			int x = sum - a[i] + j;
			if (x % 2 == 0 and x / 2 - j >= 0 and dp[x / 2 - j]) {
				san[j]++;
			}
		}
		for (int j = sum - a[i]; j >= 0; j--) {
			dp[j + a[i]] += dp[j];
		}
	}
	for (int i = 0; i <= sum; ++i) {
		if (san[i] == n) {
			jog.pb (i);
		}
	}
	cout << (int)jog.sz << endl;
	for (int i : jog) {
		cout << i << " ";
	}
}
#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...