#include <bits/stdc++.h>
#pragma optimize("g", on)
// #pragma GCC optimize ("inline")
// #pragma GCC optimize ("Ofast")
// #pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("03")
#pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,avx2,mmx,fma,avx,tune=native")
void Freopen () {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
}
using namespace std;
#define fi first
#define se second
#define int long long
const int N = 1e3 + 7, M = 5e5, mod = 1e9 + 7;
int n, a[N], dp[N];
void knapsack(int W, vector<int> v) {
for(int i = 0; i <= W; i++)dp[i] = 0;
dp[0] = 1;
for(auto j : v) {
for(int i = W; i >= j; i--) {
dp[i] = max(dp[i], dp[i - j]);
}
}
}
void solve() {
cin>>n;
vector<int> vec;
for(int i = 1; i <= n; i++) {
cin>>a[i];
vec.push_back(a[i]);
}
int need = accumulate(a + 1, a + 1 + n, 0ll);
if(need % 2 == 1) {
cout << "0\n";
return;
}
need /= 2;
knapsack(need, vec);
if(!dp[need]) {
cout << "0\n";
return;
}
need *= 2;
vector<int> an;
for(int cl = 1; cl <= 10000; cl++) {
int sm = need + cl;
bool ans = 1;
for(int i = 1; i <= n; i++) {
int W = sm - a[i];
vector<int> vv;
vv.push_back(cl);
for(int j = 1; j <= n; j++) {
if(i != j)vv.push_back(a[j]);
}
if(W % 2 == 1) {
ans = 0;
break;
}
knapsack(W / 2, vv);
if(!dp[W / 2]) {
ans = 0;
break;
}
}
if(ans)an.push_back(cl);
}
cout << an.size() << '\n';
for(auto j : an)cout << j << ' ';
cout << '\n';
}
signed main() {
// freopen("duty.in", "r", stdin);
// freopen("duty.out", "w", stdout);
ios_base::sync_with_stdio(false);
cin.tie(NULL);
//Freopen();
int T = 1;
// cin>>T;
while(T --)solve();
}
/*
please AC
*/
Compilation message (stderr)
bootfall.cpp: In function 'void Freopen()':
bootfall.cpp:10:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
10 | freopen("input.txt", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
bootfall.cpp:11:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
11 | freopen("output.txt", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
# | 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... |