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 <iostream>
#include <fstream>
#include <set>
#include <map>
#include <string>
#include <vector>
#include <bitset>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <queue>
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef long double ld;
using namespace std;
const int MX = 250005;
const int MOD = 1e9 + 7;
int n;
int a[502];
int dp[MX];
int fl[MX];
int sum = 0;
void add(int x) {
for (int i = sum; i >= 0; --i)
dp[i + x] = (dp[i + x] + dp[i]) % MOD;
sum += x;
}
void del(int x) {
sum -= x;
for (int i = 0; i <= sum; ++i) {
dp[i + x] = (dp[i + x] - dp[i] + MOD) % MOD;
}
}
int main() {
// freopen("bootfall.in", "r", stdin);
// freopen("bootfall.out", "w", stdout);
cin >> n;
for (int i = 0; i < n; ++i)
cin >> a[i];
for (int i = 1; i < MX; ++i)
fl[i] = 1;
dp[0] = 1;
for (int i = 0; i < n; ++i)
add(a[i]);
if (sum % 2 == 1 || !dp[sum / 2]) {
cout << 0 << "\n";
return 0;
}
for (int i = 0; i < n; ++i) {
del(a[i]);
for (int j = 1; j < MX; ++j) {
if ((sum + j) % 2 == 1 || !dp[(sum + j) / 2])
fl[j] = 0;
}
add(a[i]);
}
int cnt = 0;
for (int i = 0; i < MX; ++i)
cnt += fl[i];
cout << cnt << "\n";
for (int i = 0; i < MX; ++i)
if (fl[i])
cout << i << " ";
cout << "\n";
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... |