# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1128092 | BilAktauAlmansur | Bootfall (IZhO17_bootfall) | C++20 | 1094 ms | 1628 KiB |
#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 = 250000 + 7, M = 250000;
short int n, a[507];
int us[N];
void solve() {
cin>>n;
for(int i = 1; i <= n; i++) {
cin>>a[i];
}
int need = accumulate(a + 1, a + 1 + n, 0);
for(int i = 1; i <= need; i++)us[i] = 1;
if(need % 2 == 1) {
cout << "0\n";
return;
}
need /= 2;
bitset<M> st;
st[0] = 1;
for(int i = 1; i <= n; i++)st |= (st << a[i]);
if(!st[need]) {
cout << "0\n";
return;
}
need *= 2;
for(int j = 1; j <= n; j++) {
st.reset();
st[0] = 1;
for(int i = 1; i <= n; i++) {
if(i == j)continue;
st |= (st << a[i]);
}
for(int i = 1; i <= need; i++) {
if(!us[i])continue;
int W = need + i - a[j];
if(W % 2 == 1) {
us[i] = 0;
continue;
}
if(!st[W / 2]) {
us[i] = 0;
}
}
}
vector<int> ans;
for(int i = 1; i <= need; i++)if(us[i])ans.push_back(i);
cout << ans.size() << '\n';
for(auto j : ans)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);
cout.tie(NULL);
//Freopen();
int T = 1;
// cin>>T;
while(T --)solve();
}
/*
please AC
*/
Compilation message (stderr)
# | 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... |