Submission #888375

#TimeUsernameProblemLanguageResultExecution timeMemory
888375pccBootfall (IZhO17_bootfall)C++14
44 / 100
255 ms180392 KiB
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>

const int mxn = 510;
const int C = mxn*(mxn-1)/2;
int mod = 998244353;
int arr[mxn];
int dp[C];
int del[mxn][C];
int n;
int sum = 0;

inline ll mad(int a,int b){
	a += b;
	return a>=mod?a-mod:a;
}
inline ll mub(int a,int b){
	return mad(a,mod-b);
}

inline bool check(int now){
	if(sum&1)return false;
	if(!dp[sum>>1])return false;
	int tsum = sum+now;
	for(int i = 1;i<=n;i++){
		tsum -= arr[i];
		if(tsum&1)return false;
		if(tsum/2<now)return false;
		if(!del[i][tsum>>1])return false;
		tsum += arr[i];
	}
	return true;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n;
	dp[0] = 1;
	for(int i = 1;i<=n;i++){
		cin>>arr[i];
		sum += arr[i];
		for(int j = C-1;j>=arr[i];j--)dp[j] =mad(dp[j],dp[j-arr[i]]);
	}
	for(int i = 1;i<=n;i++){
		for(int j = 0;j<C;j++)del[i][j] = dp[j];
		for(int j = arr[i];j<C;j++)del[i][j] = mub(del[i][j],del[i][j-arr[i]]);
	}
	vector<int> ans;
	for(int i = 1;i<C;i++){
		if(check(i))ans.push_back(i);
	}

	vector<int> ans2;
	mod = 1e9+7;
	memset(dp,0,sizeof(dp));
	dp[0] = 1;
	for(int i = 1;i<=n;i++){
		for(int j = C-1;j>=arr[i];j--)dp[j] =mad(dp[j],dp[j-arr[i]]);
	}
	for(int i = 1;i<=n;i++){
		for(int j = 0;j<C;j++)del[i][j] = dp[j];
		for(int j = arr[i];j<C;j++)del[i][j] = mub(del[i][j],del[i][j-arr[i]]);
	}
	for(auto &i:ans){
		if(check(i))ans2.push_back(i);
	}
	swap(ans,ans2);
	ans2.clear();

	/*
	for(int i = 0;i<=10;i++)cout<<dp[i]<<' ';cout<<endl;
	cout<<sum<<endl;
	cout<<endl;
	for(int i = 1;i<=n;i++){
		for(int j = 0;j<=10;j++)cout<<del[i][j]<<' ';cout<<endl;
	}

   */

	cout<<ans.size()<<'\n';
	for(auto &i:ans)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...