# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
444345 | 2021-07-13T17:42:42 Z | KiriLL1ca | Bootfall (IZhO17_bootfall) | C++14 | 0 ms | 0 KB |
#include <bits/stdc++.h> using namespace std; /* written on phone :))))) */ const int N = 505; long long dp[N*N]; int ans[N*N]; void add (int x) { for (int i = N*N-x-1; i >= 0; i--) { dp[i+x] += dp[i]; } } void del (int x) { for (int i = x; i < N*N; i++) { dp[i] -= dp[i-x]; } } int main () { dp[0] = 1; int n; cin >> n; vector <int> a (n); int sum = 0; for (int i = 0; i < n; i++) { cin >> a[i]; sum += a[i]; add(a[i]); } if (sum & 1) { cout << 0; return 0; } if (!dp[sum >> 1]) { cout << 0; return 0; } int cnt = 0; for (int i = 0; i < n; i++) { del(a[i]); sum-=a[i]; for (int j = 1; j < N*N; j++) { int need = ((sum+j)>>1)-j; if (need >= 0 && dp[need] > 0 && (s+j) % 2 == 0) { ans[j]++; } } add(a[i]); sum+=a[i]; } for (int i = 1; i < N*N;i++) { if (ans[i] == n) cnt++; } cout << cnt << endl; for (int i = 1; i < N*N;i++) { if (ans[i] == n) cout << i << " "; } return 0; }