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 mxSm = 2503;
const int mxN = 502;
int dp[mxSm];
int a[mxN];
void solve() {
int N;
cin >> N;
vector<int> ans;
for (int i = 1; i < mxSm; i ++) {
ans.push_back(i);
}
dp[0] = 1;
int s = 0;
for (int i = 0; i < N; i ++) {
cin >> a[i];
for (int j = mxSm - 1; a[i] <= j; j --) {
dp[j] += dp[j - a[i]];
}
s += a[i];
}
if (s & 1 || !dp[s / 2]) {
cout << 0 << endl;
return;
}
for (int i = 0; i < N; i ++) {
s -= a[i];
for (int j = a[i]; j < mxSm; j ++) {
dp[j] -= dp[j - a[i]];
}
for (int j = 0; j < (int)ans.size();) {
if (s < ans[j] || (s - ans[j]) & 1 || !dp[(s - ans[j]) / 2]) {
swap(ans[j], ans.back());
ans.pop_back();
} else {
j ++;
}
}
s += a[i];
for (int j = mxSm - 1; a[i] <= j; j --) {
dp[j] += dp[j - a[i]];
}
}
sort(begin(ans),end(ans));
cout << ans.size() << endl;
for (int i : ans) {
cout << i << ' ';
}
cout << endl;
}
int main() {
solve();
}
# | 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... |