Submission #230686

#TimeUsernameProblemLanguageResultExecution timeMemory
230686johuthaBootfall (IZhO17_bootfall)C++14
100 / 100
624 ms8144 KiB
#include <iostream> #include <vector> #include <algorithm> #include <numeric> #include <cassert> #define int int64_t using namespace std; signed main() { int n; cin >> n; int m = 600*n; vector<int> v(n); for (int i = 0; i < n; i++) cin >> v[i]; int ssum = accumulate(v.begin(), v.end(), 0); vector<int> dp(m); dp[0] = 1; for (int i = 0; i < n; i++) { for (int j = m - 1; j >= v[i]; j--) dp[j] += dp[j - v[i]]; } if (ssum % 2 == 1 || (!dp[ssum/2])) { cout << "0\n"; return 0; } vector<int> res(m, 0); for (int i = 0; i < n; i++) { vector<int> poss(m); for (int j = 0; j < m; j++) { poss[j] = dp[j] - (j >= v[i] ? poss[j - v[i]] : 0); } for (int j = 0; j < m; j++) { int sm = ssum - v[i] + j; if (sm % 2 == 0 && poss[sm >> 1]) res[j]++; } } int r = count(res.begin() + 1, res.end(), n); cout << r << "\n"; for (int i = 1; i <= m; i++) if (res[i] == n) cout << i << " "; cout << "\n"; }
#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...