Submission #885984

#	Time	Username	Problem	Language	Result	Execution time	Memory
885984		boris_mihov	Bootfall (IZhO17_bootfall)	C++17	100 / 100	275 ms	4104 KiB

bootfall

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <bitset>
#include <vector>

typedef long long llong;
const int MAXS = 250000 + 10;
const int MAXN = 500 + 10;
const int MOD  = 1e9 + 13;

int n;
int a[MAXN];
int dp[MAXS];
int copy[MAXS];
int cnt[MAXS];

void solve()
{
    int sum = 0;
    dp[0] = 1;
    for (int i = 1 ; i <= n ; ++i)
    {
        sum += a[i];
        for (int j = MAXS - 1 ; j >= a[i] ; --j)
        {
            dp[j] += dp[j - a[i]];
            if (dp[j] >= MOD) dp[j] -= MOD;
        }
    }

    if ((sum & 1) || (!dp[sum / 2]))
    {
        std::cout << "0\n\n";
        return;
    }

    for (int i = 1 ; i <= n ; ++i)
    {
        for (int j = 1 ; j < MAXS ; ++j)
        {
            copy[j] = dp[j];
        }

        for (int j = 0 ; j + a[i] < MAXS ; ++j)
        {
            dp[j + a[i]] -= dp[j];
            if (dp[j + a[i]] < 0)
            {
                dp[j + a[i]] += MOD;
            }
        }

        for (int j = 0 ; j < MAXS && sum - a[i] - 2 * j > 0 ; ++j)
        {
            if (dp[j] != 0)
            {
                cnt[sum - a[i] - 2 * j]++;
            }
        }

        for (int j = 1 ; j < MAXS ; ++j)
        {
            dp[j] = copy[j];
        }
    }

    int count = 0;
    for (int i = 1 ; i < MAXS ; ++i)
    {
        count += (cnt[i] == n);
    }

    std::cout << count << '\n';
    for (int i = 1 ; i < MAXS ; ++i)
    {
        if (cnt[i] == n)
        {
            std::cout << i << ' ';
        }
    }

    std::cout << '\n';
}

void input()
{
    std::cin >> n;
    for (int i = 1 ; i <= n ; ++i)
    {
        std::cin >> a[i];
    }
}

void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIOI();
    input();
    solve();

    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