제출 #1107917

#제출 시각아이디문제언어결과실행 시간메모리
1107917alex_2008Bootfall (IZhO17_bootfall)C++14
100 / 100
806 ms4816 KiB
#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";
}
#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...