This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int maxn = 500;
// const int maxk = maxn * maxn;
const int maxk = 50;
int n;
int dp[maxk + 1];
int dp2[maxk + 1];
int weights[maxn];
int main() {
// freopen("main.in", "r", stdin);
cin >> n;
for (int i = 0; i < n; i++) cin >> weights[i];
// calc knapsack
dp[0] = 1;
for (int i = 0; i < n; i++) { // for weight
for (int j = maxk; j >= weights[i]; j--) {
dp[j] += dp[j - weights[i]];
}
}
int sm = accumulate(weights, weights + n, 0);
if (sm & 1 || !dp[sm / 2]) {
cout << 0 << endl;
return 0;
}
int works[maxk + 1];
fill(works, works + maxk + 1, 1);
// for each weight
for (int i = 0; i < n; i++) {
// remove weight
for (int j = 0; j <= maxk; j++) dp2[j] = dp[j];
for (int j = weights[i]; j <= maxk; j++) dp2[j] -= dp2[j - weights[i]];
// update works array
for (int j = 1; j <= maxk; j++) {
int SM = sm - weights[i] + j;
if (SM & 1 || !dp2[SM / 2])
works[j] = false;
}
}
int ans = accumulate(works + 1, works + maxk + 1, 0);
cout << ans << endl;
for (int i = 1; i <= maxk; i++)
if (works[i]) cout << i << ' ';
cout << endl;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |