Submission #1029927

#TimeUsernameProblemLanguageResultExecution timeMemory
1029927andrewpBootfall (IZhO17_bootfall)C++14
13 / 100
63 ms6236 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=5e2+3; 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]; } 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; } 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]; } } } vector<ll> ans; for(ll s=0; s<mxN*mxN; ++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...