# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
319216 | BeanZ | Bootfall (IZhO17_bootfall) | C++14 | 1064 ms | 996 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// I_Love_LPL
#include <bits/stdc++.h>
using namespace std;
#define task "A"
#define ll int
#define endl '\n'
const int N = 505;
const int mod = 1e9 + 7;
const int lim = 500 * 500;
bitset<lim> bit;
bitset<lim> bit2, tmp;
ll a[N];
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
if (fopen(task".inp", "r")){
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
ll n;
cin >> n;
ll sum = 0;
for (int i = 1; i <= n; i++) cin >> a[i], sum += a[i];
bit[0] = 1;
for (int i = 1; i <= n; i++){
bit |= (bit << a[i]);
}
if (bit[sum / 2] == 0) return cout << 0, 0;
for (int i = 1; i < lim; i++) bit2[i] = 1;
for (int i = 1; i <= n; i++){
bit.reset();
bit[0] = 1;
for (int j = 1; j <= n; j++){
if (i == j) continue;
bit |= (bit << a[j]);
}
tmp.reset();
for (int j = 0; j <= lim; j++){
if ((sum - j - a[i] - j) <= 0) break;
if (bit[j] && ((sum - j - a[i] - j) > 0)){
tmp[sum - j - a[i] - j] = 1;
}
}
bit2 = bit2 & tmp;
}
vector<ll> ans;
for (int i = 1; i < lim; i++){
if (bit2[i]) ans.push_back(i);
}
cout << ans.size() << endl;
for (auto j : ans) cout << j << " ";
}
/*
4
1 3 1 5
6
3 5 7 11 9 13
3
2 2 2
*/
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... |