| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1119277 | KasymK | Bootfall (IZhO17_bootfall) | C++17 | 0 ms | 0 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.
#include "bits/stdc++.h"
using namespace std;
#define ff first
#define ss second
#define all(v) v.begin(), v.end()
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define pli pair<ll, int>
#define pll pair<ll, ll>
#define tr(i, c) for(auto i = c.begin(); i != c.end(); ++i)
#define wr puts("----------------")
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
const int N = 505;
int v[N], n, sm, cnt;
bitset<N*N> dp, vis, tmp;
struct node {
int l, r;
vector<int> val;
} seg[N<<2];
void bld(int x, int l, int r){
seg[x].l = l, seg[x].r = r;
if(l==r)
return;
int mid = (l+r)>>1;
bld(x<<1, l, mid);
bld(x<<1|1, mid+1, r);
}
void upd(int x, int l, int r, int u){
if(l>r)
return;
if(l>seg[x].r or r<seg[x].l)
return;
if(l <= seg[x].l and seg[x].r <= r){
seg[x].val.pb(u);
return;
}
upd(x<<1, l, r, u);
upd(x<<1|1, l, r, u);
}
void qry(int x, bitset<N*N> wow){
for(auto i : seg[x].val)
wow=wow|(wow<<i);
if(seg[x].l==seg[x].r){
cnt++;
sm -= v[seg[x].l];
vis.set(0);
for(int i = 0; i <= sm; ++i)
if(dp[i]){
int val = abs(sm-2*i);
vis[val] = 1;
}
if(cnt==1)
tmp=vis;
else
tmp &= vis;
sm += v[seg[x].l];
return;
}
qry(x<<1, wow);
qry(x<<1|1, wow);
}
int main(){
// freopen("file.txt", "r", stdin);
scanf("%d", &n);
bld(1, 1, n);
dp[0] = 1;
for(int i = 1; i <= n; ++i){
scanf("%d", v+i), sm += v[i];
upd(1, 1, i-1, v[i]);
upd(1, i+1, n, v[i]);
dp=dp|(dp<<v[i]);
}
if(sm&1 or !dp[sm/2]){
puts("0");
return 0;
}
dp.reset();
dp[0] = 1;
qry(1, dp);
vector<int> ans;
for(int i = 0; i <= sm; ++i)
if(tmp[i])
ans.pb(i);
printf("%d\n", (int)ans.size());
for(auto i : ans)
printf("%d ", i);
puts("");
return 0;
}