Submission #366153

#TimeUsernameProblemLanguageResultExecution timeMemory
366153nicolaalexandraBootfall (IZhO17_bootfall)C++14
100 / 100
414 ms4580 KiB
#include <bits/stdc++.h> #define DIM 502 using namespace std; int dp[DIM*DIM],dp2[DIM*DIM]; int v[DIM],f[DIM*DIM]; vector <int> sol,w,w2; int n,i,j,sum_total; int main (){ //ifstream cin ("date.in"); //ofstream cout ("date.out"); cin>>n; for (i=1;i<=n;i++){ cin>>v[i]; sum_total += v[i]; } if (sum_total % 2){ cout<<"0"; return 0; } /// dp[i] - in cate moduri pot sa obtin suma asta dp[0] = 1; for (i=1;i<=n;i++){ for (j=sum_total-v[i];j>=0;j--){ if (dp[j]) dp[j+v[i]] += dp[j]; } } if (!dp[sum_total/2]){ cout<<"0"; return 0; } for (i=1;i<=n;i++){ memcpy (dp2,dp,sizeof dp2); for (j=0;j<=sum_total-v[i];j++) if (dp2[j]) dp2[j+v[i]] -= dp2[j]; int sum = sum_total - v[i]; for (j=1;j<=sum;j++){ if ( (sum + j)%2 ) continue; int val = (sum + j)/2; /// exista suma asta? if (dp2[val]) f[j]++; } } for (i=1;i<=sum_total;i++){ if (f[i] == n) sol.push_back(i); } cout<<sol.size()<<"\n"; for (auto it : sol) cout<<it<<" "; 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...