Submission #85409

#	Time	Username	Problem	Language	Result	Execution time	Memory
85409		ToadDaveski	Bootfall (IZhO17_bootfall)	C++14	100 / 100	477 ms	6532 KiB

bootfall

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll a[501],dp[501*501],sum=0,isA[501*501];
vector <ll> answer;
void add(ll x)
{
    sum+=x;
    for(ll i=500*500;i>=x;i--)
        dp[i]+=dp[i-x];
}
void del(ll x)
{
    sum-=x;
    for(ll i=x;i<=500*500;i++)
        dp[i]-=dp[i-x];
}
int main()
{
    ll n,m,i,j;
    cin>>n;
    for(i=1;i<=n;i++)
        cin>>a[i];
    dp[0]=1;
    for(i=1;i<=n;i++)
        add(a[i]);
    if (sum%2 || !dp[sum/2])
    {
        cout<<0;
        return 0;
    }
    for(i=1;i<=n;i++)
    {
        del(a[i]);
        for(j=1;j<=500*500;j++)
            if ((sum+j)%2 ||  !dp[(sum+j)/2])
            isA[j]=1;
        add(a[i]);
    }
    for(i=1;i<=500*500;i++)
        if (!isA[i]) answer.push_back(i);
    cout<<answer.size()<<endl;
    for(ll toad: answer)
        cout<<toad<<" ";
    return 0;
}

Compilation message (stderr)

bootfall.cpp: In function 'int main()':
bootfall.cpp:20:10: warning: unused variable 'm' [-Wunused-variable]
     ll n,m,i,j;
          ^

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