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>
#define ios ios_base::sync_with_stdio(0); cin.tie(0);
#define pb push_back
using namespace std;
typedef int ll;
const int N = 5e2 + 11;
const int MAX = 1e6;
short int n;
int s;
short int a[N];
bool ok[500 * 500 + 3];
bitset < 500 * 500 + 3 > d;
void sol(){
cin >> n, d[0] = 1;
for(ll i = 1; i <= 500 * 500; i++) ok[i] = 1;
for(ll i = 1; i <= n; i++) cin >> a[i], d |= (d << a[i]), s += a[i];
if(s % 2 || d[s / 2] == 0){
cout << "0\n";
return;
}
for(short int i = 1; i <= n; i++){
bitset < 500 * 500 + 3 > dp;
dp[0] = 1, s = 0;
for(short int j = 1; j <= n; j++)
if(i != j)
dp |= (dp << a[j]), s += a[j];
for(int j = 1; j <= 500 * 500; j++){
if(s < j || (s - j) % 2) ok[j] = 0;
else ok[j] &= dp[(s - j) / 2];
}
}
vector < int > ans;
for(int i = 1; i <= 500 * 500; i++){
if(ok[i]){
ans.pb(i);
}
}
cout << ans.size() << '\n';
for(int x : ans) cout << x << ' ';
}
signed main(){
ios
sol();
// slow();
// stress();
}
# | 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... |