Submission #1107917

#	Time	Username	Problem	Language	Result	Execution time	Memory
1107917		alex_2008	Bootfall (IZhO17_bootfall)	C++14	100 / 100	806 ms	4816 KiB

bootfall

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#define ff first
#define ss second
typedef long long ll;
using namespace std;
const int P1 = 727196341;
const int P2 = 271915031;
const int N = 500 + 10;
int a[N];
int dp1[N * N];
int dp2[N * N];
int cnt[N * N];
void add(int x, int k) {
	for (int i = k; i >= x; i--) {
		dp1[i] = (dp1[i - x] + dp1[i]) % P1;
		dp2[i] = (dp2[i - x] + dp2[i]) % P2;
	}
}
void sub(int x, int sm) {
	for (int i = x; i <= sm; i++) {
		dp1[i] = (dp1[i] - dp1[i - x] + P1) % P1;
		dp2[i] = (dp2[i] - dp2[i - x] + P2) % P2;
	}
}
int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	int n;
	cin >> n;
	int sm = 0;
	dp1[0] = 1;
	dp2[0] = 1;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];		
		sm += a[i];
		add(a[i], sm);
	}
	if (sm % 2 != 0) {
		cout << 0 << "\n";
		return 0;
	}
	if (dp1[sm / 2] == 0 && dp2[sm / 2] == 0) {
		cout << 0 << "\n";
		return 0;
	}
	for (int i = 1; i <= n; i++) {
		sub(a[i], sm);
		sm -= a[i];
		for (int i = 0; 2 * i < sm; i++) {
			if ((dp1[i] != 0 || dp2[i] != 0)) {
				cnt[sm - 2 * i]++;
			}
		}		
		sm += a[i];
		add(a[i], sm);
	}
	vector <int> ans;
	for (int i = 1; i < N * N; i++) {
		if (cnt[i] == n) ans.push_back(i);
	}
	cout << (int)ans.size() << "\n";
	for (auto it : ans) {
		cout << it << " ";
	}
	cout << "\n";
}

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