This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define replr(i, a, b) for (int i = int(a); i <= int(b); ++i)
#define reprl(i, a, b) for (int i = int(a); i >= int(b); --i)
#define rep(i, n) for (int i = 0; i < int(n); ++i)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VPI;
typedef vector<VI> VVI;
typedef vector<VPI> VVPI;
typedef pair<ll, ll> PLL;
typedef vector<ll> VL;
typedef vector<PLL> VPL;
typedef vector<VL> VVL;
typedef vector<VPL> VVPL;
template<class T> T setmax(T& a, T b) {if (a < b) return a = b; return a;}
template<class T> T setmin(T& a, T b) {if (a < b) return a; return a = b;}
const int MAXN = 100;
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
const int MAXSUM = 500 * 500;
typedef bitset<MAXSUM+1> bit;
bit f(VI& v, int excludant = -1) {
bit ans;
ans[0] = 1;
rep(i, v.size()) {
if (i == excludant) continue;
ans |= (ans << v[i]);
}
return ans;
}
void solve() {
int n;
cin >> n;
VI a(n);
int sum = 0;
for (int& x : a) cin >> x, sum += x;
bit pos = f(a);
if (sum % 2 || !pos[sum/2]) cout << 0 << endl;
else {
bit ans = ~bit(0);
rep(i, n) {
bit pos = f(a, i);
for (int x = 0; x <= MAXSUM; x++) {
int newsum = (sum - a[i] + x);
/* if (newsum % 2 || newsum/2 < x || (!pos[newsum/2] && !pos[newsum/2 - x])) { */
if (newsum % 2 || newsum/2 < x || !pos[newsum/2]) {
ans[x] = false;
}
}
}
VI v;
for (int i = 0; i <= MAXSUM; i++) {
if (ans[i]) v.pb(i);
}
cout << v.size() << endl;
for (int x : v) cout << x << " ";
cout << endl;
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
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... |