Submission #472833

#	Time	Username	Problem	Language	Result	Execution time	Memory
472833		ogibogi2004	Bootfall (IZhO17_bootfall)	C++14	100 / 100	610 ms	84028 KiB

bootfall

#include<bits/stdc++.h>
using namespace std;
const int MAXN=512;
int n,a[MAXN],sum;
struct node
{
    vector<int>vals;
    bitset<MAXN*MAXN>possible;
};
node tree[4*MAXN];
bitset<MAXN*MAXN>without[MAXN];
void update(int l,int r,int idx,int ql,int qr,int val)
{
    if(l>qr)return;
    if(r<ql)return;
    if(l>=ql&&r<=qr)
    {
        tree[idx].vals.push_back(val);
        return;
    }
    int mid=(l+r)/2;
    update(l,mid,idx*2,ql,qr,val);
    update(mid+1,r,idx*2+1,ql,qr,val);
}
void build(int l,int r,int idx)
{
    tree[idx].possible[0]=1;
    for(auto xd:tree[idx].vals)
    {
        tree[idx].possible=tree[idx].possible|(tree[idx].possible<<xd);
    }
    if(l==r)
    {
        without[l]=tree[idx].possible;
        return;
    }
    int mid=(l+r)/2;
    tree[idx*2].possible=tree[idx].possible;
    tree[idx*2+1].possible=tree[idx].possible;
    build(l,mid,idx*2);
    build(mid+1,r,idx*2+1);
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++){cin>>a[i];sum+=a[i];}
    if(sum%2==1)
    {
        cout<<"0\n";
        return 0;
    }
    for(int i=1;i<=n;i++)
    {
        update(1,n+1,1,1,i-1,a[i]);
        update(1,n+1,1,i+1,n+1,a[i]);
    }
    build(1,n+1,1);
    if(without[n+1][sum/2]==0)
    {
        cout<<"0\n";
        return 0;
    }
    //cout<<"?\n";
    vector<int>ans;
    for(int cand=1;cand<=sum;cand++)
    {
        bool ok=1;
        for(int i=1;i<=n;i++)
        {
            int sum1=sum+cand-a[i];
            if(sum1%2!=0)
            {
                ok=0;break;
            }
            if(without[i][sum1/2]==0)
            {
                ok=0;break;
            }
        }
        if(ok)ans.push_back(cand);
    }
    cout<<ans.size()<<endl;
    for(auto xd:ans)
    {
        cout<<xd<<" ";
    }
    cout<<endl;
return 0;
}

• Subtask 1: 6 / 6
• Subtask 2: 7 / 7
• Subtask 3: 15 / 15
• Subtask 4: 16 / 16
• Subtask 5: 21 / 21
• Subtask 6: 35 / 35