Submission #650286

#	Time	Username	Problem	Language	Result	Execution time	Memory
650286		sofija6	Bootfall (IZhO17_bootfall)	C++14	100 / 100	756 ms	4180 KiB

bootfall

#include <bits/stdc++.h>
#define ll long long
#define MAXN 510
#define MAXS 250010
#define MOD 1000000007
using namespace std;
ll dp[MAXS],sum,a[MAXN];
bool yes[MAXS];
void Add(ll x)
{
    for (ll i=MAXS-5;i>=x;i--)
        dp[i]=(dp[i]+dp[i-x])%MOD;
}
void Remove(ll x)
{
    for (ll i=x;i<=MAXS-5;i++)
        dp[i]=(dp[i]-dp[i-x]+MOD)%MOD;
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll n;
    cin >> n;
    dp[0]=1;
    for (ll i=1;i<=n;i++)
    {
        cin >> a[i];
        sum+=a[i];
    }
    for (ll i=1;i<=n;i++)
        Add(a[i]);
    if (sum&1 || !dp[sum/2])
    {
        cout << 0 << "\n";
        return 0;
    }
    for (ll i=1;i<MAXS;i++)
        yes[i]=true;
    for (ll i=1;i<=n;i++)
    {
        Remove(a[i]);
        for (ll j=1;j<MAXS;j++)
        {
            if (!yes[j])
                continue;
            if ((sum+j-a[i])&1 || !dp[(sum+j-a[i])/2])
                yes[j]=false;
        }
        Add(a[i]);
    }
    vector<ll> ans;
    for (ll i=1;i<MAXS;i++)
    {
        if (yes[i])
            ans.push_back(i);
    }
    cout << ans.size() << "\n";
    for (ll i=0;i<ans.size();i++)
        cout << ans[i] << " ";
    return 0;
}

Compilation message (stderr)

bootfall.cpp: In function 'int main()':
bootfall.cpp:58:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     for (ll i=0;i<ans.size();i++)
      |                 ~^~~~~~~~~~~

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