/*
_ _ _ _ _ __ _____ _____ _
| | | | _ | | | | | | / | |____ | ___(_)
__ _ _ _| |_| |__ ___ _ __(_) | |__ __ _| | __ _ _ __ __| | __ _ `| | / /___ \ _ __ _
/ _` | | | | __| '_ \ / _ \| '__| | '_ \ / _` | |/ _` | '_ \ / _` |/ _` | | | \ \ \ \ |/ _` |
| (_| | |_| | |_| | | | (_) | | _ | |_) | (_| | | (_| | | | | (_| | (_| | _| |_.___/ /\__/ / | (_| |
\__,_|\__,_|\__|_| |_|\___/|_| (_) |_.__/ \__,_|_|\__,_|_| |_|\__,_|\__,_| \___/\____/\____/|_|\__, |
| |
|_|
__ _ __ _ _ __ ___ __ ___ _________ ___
/ _` |/ _` | | '_ ` _ \ / _` \ \ / /_ / _ \/ __|
| (_| | (_| | | | | | | | (_| |\ V / / / __/\__ \
\__, |\__, | |_| |_| |_|\__,_| \_/ /___\___||___/
| | | |
|_| |_|
* */
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
template<class T>
istream& operator>>(istream &in, vector<T> &v){
for(auto &to: v) in >> to;
return in;
}
template<class T>
ostream& operator<<(ostream &out, const vector<T> &v){
for(auto &to: v) out << v << ' ';
return out;
}
template<class U, class V>
istream& operator>>(istream &in, pair<U, V> &v){
in >> v.first >> v.second;
return in;
}
template<class U, class V>
ostream& operator<<(ostream &out, const pair<U, V> &v){
out << v.first << ' ' << v.second;
return out;
}
#ifdef DEBUG
#define dbg(x) cout << "debug:" << __LINE__ << ' ' << #x << "=" << x
#else
#define dbg(x) 42
#endif
int solve(){
int n;
cin >> n;
vector<int> v(n);
cin >> v;
int sm = 0;
for(int i = 0; i < n; i++)
sm += v[i];
vector<bitset<72902> > dpp(n + 1);
vector<bitset<72902> > dps(n + 1);
dpp[0][0] = 1;
dps[n][0] = 1;
for(int i = 1; i <= n; i++){
dpp[i] = dpp[i - 1];
dpp[i] |= (dpp[i - 1] << v[i - 1]);
}
for(int i = n - 1; i >= 0; i--){
dps[i] = dps[i + 1];
dps[i] |= (dps[i + 1] << v[i]);
}
if(!dpp[n][sm / 2]){
cout << 0;
return 0;
}
set<int> possible;
for(int j = 1; j <= sm + 5; j++) {
if(j % 2 != v[0] % 2) continue;
possible.insert(j);
}
bitset<72902> crr;
for(int i = 0; i < n; i++){
if(possible.empty()) break;
for(int j = 0; j <= (sm - v[i] + *possible.rbegin()) / 2; j++){
if((i && dpp[i][j] ^ dpp[i - 1][j]) || (!i && dpp[i][j]))
crr |= (dps[i + 1] << j);
}
vector<int> bad;
for(auto to: possible){
int full = (sm - v[i] + to);
if(full % 2) bad.push_back(to);
else if(!(crr[full / 2] && crr[full / 2 - to])){
bad.push_back(to);
}
}
for(auto to: bad) possible.erase(to);
}
cout << possible.size() << endl;
for(auto to: possible){
cout << to << ' ';
}
return 0;
}
signed main() {
#ifdef DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t = 1;
// cin >> t;
while(t --> 0){
assert(solve() == 0);
cout << endl;
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
748 KB |
Execution killed with signal 7 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
748 KB |
Execution killed with signal 7 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
748 KB |
Execution killed with signal 7 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
748 KB |
Execution killed with signal 7 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
748 KB |
Execution killed with signal 7 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
748 KB |
Execution killed with signal 7 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
