Submission #1128066

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128066		batyi	Money (IZhO17_money)	C++20	0 / 100	0 ms	320 KiB

money

/*
|01|11|2010|
*/
#include <bits/stdc++.h>
#define ll long long
#define int ll
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define sp setprecision
#define stl(v) v.begin(),v.end()
#define stlr(v) v.rbegin(),v.rend()
#define b1cnt __builtin_popcount

using namespace std;

const int N=555;
const int mod=1e9+7;
const int inf=1e18;
const int M=55;

int n;
int a[N],b[N];
int dp[N][122502];

void prob(){
	cin>>n;
	int sum=0;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		b[i]=a[i];
		sum+=a[i];
	}
	if(sum%2==1){
		cout<<0;
		return;
	}
	int x=sum/2;
	dp[0][0]=1;
	for(int i=1;i<=n;i++){
		for(int j=0;j<=x;j++){
			if(a[i]<=j) dp[i][j]=(dp[i-1][j] || dp[i-1][j-a[i]]);
			else dp[i][j]=dp[i-1][j];
		}
	}
	if(!dp[n][x]){
		cout<<0;
		return;
	}
	sort(a+1,a+1+n);
	int mx=0;
	for(int i=2;i<=n;i++) mx+=a[i];
	vector<int> ans;
	for(int w=1;w<=mx;w++){
		bool ok=1;
		for(int id=1;id<=n;id++){
			b[id]=w;
			int sum2=sum;
			sum2-=a[id];
			sum2+=b[id];
			if(sum2%2==1){
				b[id]=a[id];
				ok=0;
				break;
			}
			for(int i=1;i<=n;i++){
				for(int j=0;j<=sum2/2;j++) dp[i][j]=0;
			}
			dp[0][0]=1;
			for(int i=1;i<=n;i++){
				for(int j=0;j<=sum2/2;j++){
					if(b[i]<=j) dp[i][j]=(dp[i-1][j] || dp[i-1][j-b[i]]);
					else dp[i][j]=dp[i-1][j];
				}
			}
			b[id]=a[id];
			if(!dp[n][sum2/2]) ok=0;
		}
		if(ok) ans.pb(w);
	}
	cout<<ans.size()<<"\n";
	for(int i:ans) cout<<i<<" ";
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t2=1;
//    cin>>t2; 
    for(int test=1;test<=t2;test++){
        prob();
    }
}

//       ▄▌▐▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀█|
//    ▄▄██▌█════Фура═с═Кодами════█|
// ▄▄▄▌▐██▌█═Приехала═Разгружаем═█|
// ███████▌█▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄█|
// ▀(@)▀▀▀▀▀▀▀(@)(@)▀▀▀▀▀▀▀▀▀▀▀(@)

• Subtask 1: 0 / 9
• Subtask 2: 0 / 16
• Subtask 3: 0 / 20
• Subtask 4: 0 / 55