Submission #1037225

#TimeUsernameProblemLanguageResultExecution timeMemory
1037225ByeWorldBootfall (IZhO17_bootfall)C++14
13 / 100
1055 ms16844 KiB
#include <bits/stdc++.h> #pragma GCC optimize("O3") #define int long long #define ll long long #define pb push_back #define fi first #define se second #define lf (id<<1) #define rg ((id<<1)|1) #define md ((l+r)>>1) using namespace std; typedef pair<int,int> pii; typedef pair<int,pii> ipii; const int MAXN = 505; const int MAXA = 250100; const int MAXK = 1e5+10; const int INF = 1e18+10; void chmn(int &a, int b){ a = min(a, b); } int n; int a[MAXN], mx; vector <int> ans; bool dp[MAXN][MAXA]; void cek(int x){ bool can = 1; for(int i=1; i<=n; i++){ int sum = x; vector <int> vec; vec.pb(-1); for(int j=1; j<=n; j++) if(i!=j) vec.pb(a[j]), sum += a[j]; vec.pb(x); if(sum%2 == 1){ can = 0; break; } for(int j=0; j<=n; j++) for(int k=0; k<=sum/2; k++) dp[j][k] = 0; dp[0][0] = 1; // for(auto in : vec) cout << in << ' '; // cout << "xx\n"; for(int j=1; j<=n; j++){ for(int k=0; k<=sum/2; k++){ dp[j][k] = dp[j-1][k]; if(k>=vec[j]) dp[j][k] |= dp[j-1][k-vec[j]]; } } // cout << x << ' ' << dp[n][sum/2] << ' '<< sum<< " pp\n"; can &= dp[n][sum/2]; } if(can) ans.pb(x); } signed main(){ // ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; for(int i=1; i<=n; i++){ cin >> a[i]; mx += a[i]; } dp[0][0] = 1; for(int j=1; j<=n; j++){ for(int k=0; k<=mx/2; k++){ dp[j][k] = dp[j-1][k]; if(k>=a[j]) dp[j][k] |= dp[j-1][k-a[j]]; } } if(mx%2==1 || !dp[n][mx/2]){ cout << "0\n"; exit(0); } for(int i=1; i<=mx; i++) cek(i); cout << ans.size() << '\n'; for(auto in : ans) cout << in << ' '; cout << '\n'; }
#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...