Submission #645857

#	Time	Username	Problem	Language	Result	Execution time	Memory
645857		boris_mihov	Bootfall (IZhO17_bootfall)	C++17	28 / 100	1086 ms	844 KiB

bootfall

#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
#include <bitset>
#include <set>
#include <map>

typedef long long llong;
const int MAXN = 500 + 10;
const int MAXSUM = 500*500*2 + 10;
const int INF  = 1e9;

int a[MAXN], n;
std::vector <int> values;
std::bitset <MAXSUM> bs, ans;
void getBitset(int missing)
{
    bs.reset();
    bs[MAXSUM / 2] = 1;
    for (int i = 1 ; i <= n ; ++i)
    {
        if (i == missing) continue;
        bs = ((bs << a[i]) | (bs >> a[i]));
    }
}

void solve()
{
    ans.set();
    bs[MAXSUM / 2] = 1;
    for (int i = 1 ; i <= n ; ++i)
    {
        bs = ((bs << a[i]) | (bs >> a[i]));
    }

    if (!bs[MAXSUM / 2])
    {
        std::cout << 0 << '\n';
        return;
    }

    for (int i = 1 ; i <= n ; ++i)
    {
        getBitset(i);
        ans &= bs;
    }

    for (int i = 1 ; i <= MAXSUM - MAXSUM/2 - 1 ; ++i)
    {
        if (ans[MAXSUM / 2 + i] || ans[MAXSUM / 2 - i])
        {
            values.push_back(i);
        }
    }

    std::cout << values.size() << '\n';
    for (const int &i : values)
    {
        std::cout << i << ' '; 
    }

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

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

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

int main()
{
    fastIO();
    read();
    solve();

    return 0;
}

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