Submission #1029937

#TimeUsernameProblemLanguageResultExecution timeMemory
1029937andrewpBootfall (IZhO17_bootfall)C++14
13 / 100
41 ms6412 KiB
#include <bits/stdc++.h> using namespace std; #define ll int64_t #define ar array #define dbg(x) cerr << #x << ": " << x << "\n"; const int mxN=503; ll n, a[mxN], dp[mxN*mxN][2], brM[mxN*mxN]; int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n; ll sum=0; for(ll i=1; i<=n; ++i) { cin >> a[i]; sum+=a[i]; } for(int i=0; i<mxN*mxN; ++i) { for(int j=0; j<2; ++j) { dp[i][j]=0; } brM[i]=0; } dp[0][0]=1; for(ll i=1; i<=n; ++i) { for(ll s=mxN*mxN-1; s>=a[i]; --s) { dp[s][0]+=dp[s-a[i]][0]; } } if(sum%2==1) { cout << 0 << "\n"; return 0; } if(dp[sum/2][0]==0) { cout << 0 << "\n"; return 0; } vector<ll> ans; for(ll i=1; i<=n; ++i) { for(ll s=0; s<mxN*mxN; ++s) { dp[s][1]=dp[s][0]; } for(ll s=0; s<mxN*mxN-a[i]; ++s) { dp[s+a[i]][1]-=dp[s][1]; } for(ll s=0; s<mxN*mxN; ++s) { ll get=s+sum-a[i]; if((get%2==0)&&(get/2>=s)&&(dp[get/2-s][1]>0)) { ++brM[s]; if(brM[s]==n) ans.push_back(s); } } } cout << ans.size() << "\n"; for(ll x:ans) 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...