# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
319238 | BeanZ | Bootfall (IZhO17_bootfall) | C++14 | 212 ms | 3300 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;
ll a[N];
bool chk[505];
const int lim = 500 * 500 + 5;
const int lim2 = 500 * 500 / 2 + 1;
bitset<lim> bit2, tmp;
ll sum = 0;
void solve(ll l, ll r, bitset<lim> bit){
if (l == r){
tmp.reset();
for (int j = 0; j <= lim; j++){
if ((sum - j - a[l] - j) <= 0) break;
if (bit[j] && ((sum - j - a[l] - j) > 0)){
tmp[sum - j - a[l] - j] = 1;
}
}
bit2 = bit2 & tmp;
return;
}
ll mid = (l + r) >> 1;
bitset<lim> L, R;
L = bit;
R = bit;
for (int i = mid + 1; i <= r; i++) R |= (R << a[i]);
for (int i = l; i <= mid; i++) L |= (L << a[i]);
solve(l, mid, R);
solve(mid + 1, r, L);
}
bitset<lim> bit;
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;
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;
bit.reset();
bit[0] = 1;
solve(1, n, bit);
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... |