| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1128088 | batyi | Bootfall (IZhO17_bootfall) | C++20 | 0 ms | 0 KiB |
/*
|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=352;
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;
break;
}
}
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();
}
}
// ▄▌▐▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀█|
// ▄▄██▌█════Фура═с═Кодами════█|
// ▄▄▄▌▐██▌█═Приехала═Разгружаем═█|
// ███████▌█▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄█|
// ▀(@)▀▀▀▀▀▀▀(@)(@)▀▀▀▀▀▀▀▀▀▀▀(@)