Submission #867300

#	Time	Username	Problem	Language	Result	Execution time	Memory
867300		Halym2007	Bootfall (IZhO17_bootfall)	C++11	100 / 100	334 ms	3528 KiB

bootfall

#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 << " ";
	}
}

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