Submission #346815

#TimeUsernameProblemLanguageResultExecution timeMemory
346815SeDunionBootfall (IZhO17_bootfall)C++17
100 / 100
485 ms3052 KiB
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 505;
const int MX = 500 * 500 + 5;

const int mod = 1e9 + 7;
int a[N], d[MX], cnt[MX], Sum;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int n;
	cin >> n;
	d[0] = 1;
	for (int i = 1 ; i <= n ; ++ i) {
		cin >> a[i];
		Sum += a[i];
		for (int j = MX - 1 ; j >= a[i] ; -- j) {
			d[j] += d[j - a[i]];
			d[j] -= d[j] >= mod ? mod : 0;
		}
	}
	if (Sum & 1 || !d[Sum / 2]) return cout << "0", 0;
	for (int i = 1 ; i <= n ; ++ i) {
		int Now = Sum - a[i];
		//cout << i << " " << Now << endl;
		for (int j = a[i] ; j < MX ; ++ j) {
			d[j] -= d[j - a[i]];
			d[j] += d[j] < 0 ? mod : 0;
		}
		for (int j = Now & 1 ; j < MX ; j += 2) {
			int Cur = Now + j;
			cnt[j] += j <= (Cur >> 1) && !!d[(Cur >> 1) - j];
		}
		for (int j = MX - 1 ; j >= a[i] ; -- j) {
			d[j] += d[j - a[i]];
			d[j] -= d[j] >= mod ? mod : 0;
		}
	}
	int Cnt = 0;
	for (int i = 0 ; i < MX ; ++ i) Cnt += cnt[i] == n;
	cout << Cnt << "\n";
	for (int i = 0 ; i < MX ; ++ i) if (cnt[i] == n) 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...