Submission #906880

#TimeUsernameProblemLanguageResultExecution timeMemory
906880daoquanglinh2007Bootfall (IZhO17_bootfall)C++17
65 / 100
449 ms3156 KiB
#include <bits/stdc++.h>
using namespace std;

const int NM = 500, MOD = 1e9+321;

int N, a[NM+5], sum = 0, dp[NM*NM+5], dp0[NM*NM+5], K = 0;
bool ok[NM*NM+5];

void add(int x){
	for (int i = NM*NM; i >= x; i--)
		dp[i] = (dp[i]+dp[i-x])%MOD;
}

void remove(int x){
	for (int i = x; i <= NM*NM; i++)
		dp[i] = (dp[i]+MOD-dp[i-x])%MOD;
}

void solve(int t){
	for (int i = 0; i <= NM*NM; i++) dp[i] = dp0[i];
	remove(a[t]);
	
	for (int i = 1; i <= NM*NM; i++)
		if ((sum-a[t]+i)%2 != 0 || (sum-a[t]+i)/2-i < 0 || !dp[(sum-a[t]+i)/2-i]) ok[i] = 0;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin >> N;
	dp[0] = 1;
	for (int i = 1; i <= N; i++){
		cin >> a[i];
		sum += a[i];
		add(a[i]);
	}
	if (sum%2 != 0 || !dp[sum/2]){
		cout << "0\n";
		return 0;
	}
	for (int i = 0; i <= NM*NM; i++){
		dp0[i] = dp[i];
		ok[i] = 1;
	}
	for (int i = 1; i <= N; i++)
		solve(i);
		
	for (int i = 1; i <= NM*NM; i++) K += ok[i];
	
	cout << K << '\n';
	for (int i = 1; i <= NM*NM; i++)
		if (ok[i]) cout << i << ' ';
		
	return 0;
}
#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...