# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
333001 | Dymo | Bootfall (IZhO17_bootfall) | C++14 | 1 ms | 492 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 pb push_back
#define eb emplace_back
#define ll long long
#define pll pair<ll,ll>
#define ff first
#define ss second
#define endl "\n"
const ll maxn=500*500+10;
const ll mod =1e9+7 ;
const ll base=1e18;
const ll block=1000;
/// con 0 ngay nua
/// zesitahn
ll a[maxn];
bitset<maxn> st1;
ll t=0;
void dosth(ll l,ll r,bitset<maxn> st)
{
if (l==r)
{
bitset<maxn>chk;
for (int i=1;i<maxn;i++)
{
ll cl=t-a[l]-i;
if (cl<0) break;
if (cl%2==0)
{
cl/=2;
if (i==4)
{
cout <<cl<<endl;
}
if (st[cl]==1) chk[i]=1;
}
}
st1&=chk;
return ;
}
ll mid=(l+r)/2;
auto nxt=st;
for (int i=mid+1;i<=r;i++)
{
nxt|=(nxt<<a[i]);
}
dosth(l,mid,nxt);
nxt=st;
for (int i=l;i<=mid;i++)
{
nxt|=(nxt<<a[i]);
}
dosth(mid+1, r, nxt);
}
bool chk(ll n)
{
if (t%2==1) return false;
bitset<maxn> st;
for (int i=1;i<=n;i++)
{
st|=(st<<a[i]);
}
return st[t/2];
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
if (fopen("queue.inp", "r"))
{
freopen("queue.inp", "r", stdin);
freopen("queue.out", "w", stdout);
}
ll n;
cin>> n;
for (int i=1;i<=n;i++)
{
cin>>a[i];
t+=a[i];
}
if (!chk(n))
{
cout <<0;
return 0;
}
bitset<maxn> st;
st[0]=1;
for (int i=1;i<maxn;i++)
{
st1[i]=1;
}
dosth(1,n,st);
vector<ll> ans;
for (int i=1;i<maxn;i++)
{
if (st1[i]) ans.pb(i);
}
cout <<ans.size()<<endl;
for (auto to:ans)
{
cout <<to<<" ";
}
}
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... |