Submission #85409

#TimeUsernameProblemLanguageResultExecution timeMemory
85409ToadDaveskiBootfall (IZhO17_bootfall)C++14
100 / 100
477 ms6532 KiB
#include <bits/stdc++.h> #define ll long long using namespace std; ll a[501],dp[501*501],sum=0,isA[501*501]; vector <ll> answer; void add(ll x) { sum+=x; for(ll i=500*500;i>=x;i--) dp[i]+=dp[i-x]; } void del(ll x) { sum-=x; for(ll i=x;i<=500*500;i++) dp[i]-=dp[i-x]; } int main() { ll n,m,i,j; cin>>n; for(i=1;i<=n;i++) cin>>a[i]; dp[0]=1; for(i=1;i<=n;i++) add(a[i]); if (sum%2 || !dp[sum/2]) { cout<<0; return 0; } for(i=1;i<=n;i++) { del(a[i]); for(j=1;j<=500*500;j++) if ((sum+j)%2 || !dp[(sum+j)/2]) isA[j]=1; add(a[i]); } for(i=1;i<=500*500;i++) if (!isA[i]) answer.push_back(i); cout<<answer.size()<<endl; for(ll toad: answer) cout<<toad<<" "; return 0; }

Compilation message (stderr)

bootfall.cpp: In function 'int main()':
bootfall.cpp:20:10: warning: unused variable 'm' [-Wunused-variable]
     ll n,m,i,j;
          ^
#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...