Submission #1084215

#TimeUsernameProblemLanguageResultExecution timeMemory
1084215elotelo966Bootfall (IZhO17_bootfall)C++17
100 / 100
359 ms5840 KiB
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define OYY LLONG_MAX
#define mod 998244353
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define FOR for(int i=1;i<=n;i++)
#define mid (start+end)/2
#define lim 250005
#define fi first
#define se second

int dp[lim];

int cev[lim];

int sum;

int32_t main(){
	faster
	int n;cin>>n;
	int dizi[n];
	FOR{
		cin>>dizi[i];
		sum+=dizi[i];
	}
	
	dp[0]=1;
	
	FOR{
		for(int j=sum;j>=dizi[i];j--){
			dp[j]+=dp[j-dizi[i]];
		}
	}
	
	if(sum&1 || dp[sum/2]==0){
		cout<<0<<'\n';
		return 0;
	}
	
	FOR{
		for(int j=dizi[i];j<=sum;j++){
			dp[j]-=dp[j-dizi[i]];
		}
		for(int j=1;j<=sum;j++){
			int cur_sum=sum-dizi[i]+j;
			if(cur_sum%2==0 && dp[cur_sum/2])cev[j]++;
		}
		for(int j=sum;j>=dizi[i];j--){
			dp[j]+=dp[j-dizi[i]];
		}
	}
	
	vector<int> cevv;
	
	for(int i=1;i<=sum;i++){
		if(cev[i]==n)cevv.push_back(i);
	}
	
	cout<<cevv.size()<<'\n';
	
	for(auto x:cevv){
		cout<<x<<" ";
	}
	
	cout<<'\n';
	
	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...