Submission #1207054

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207054		borisAngelov	Bootfall (IZhO17_bootfall)	C++20	65 / 100	1044 ms	1260 KiB

bootfall

#include <bits/stdc++.h>

using namespace std;

const int maxn = 505;
const int MAX = 500 * 500 + 5;

int n, sum = 0;
int a[maxn];

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

int main()
{
    fastIO();

    cin >> n;

    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
        sum += a[i];
    }

    bitset<MAX> dp;
    dp.reset();
    dp[0] = 1;

    for (int i = 1; i <= n; ++i)
    {
        dp |= (dp << a[i]);
    }

    if (sum % 2 == 1 || dp[sum / 2] != 1)
    {
        cout << 0 << endl;
        return 0;
    }

    vector<int> whichDiffs;
    vector<bool> isPossible;

    for (int i = 1; i <= n; ++i)
    {
        dp.reset();
        dp[0] = 1;

        for (int j = 1; j <= n; ++j)
        {
            if (j != i)
            {
                dp |= (dp << a[j]);
            }
        }

        if (i == 1)
        {
            for (int j = 0; j <= (sum - a[i]) / 2; ++j)
            {
                if (dp[j] == 1)
                {
                    whichDiffs.push_back((sum - a[i]) - 2 * j);
                }
            }

            isPossible.resize(whichDiffs.size());
            for (int j = 0; j < isPossible.size(); ++j)
            {
                isPossible[j] = true;
            }
        }
        else
        {
            for (int j = 0; j < whichDiffs.size(); ++j)
            {
                int d = whichDiffs[j];
                if ((sum - a[i] - d) < 0) isPossible[j] = false;
                else if ((sum - a[i] - d) % 2 == 1) isPossible[j] = false;
                else if (dp[(sum - a[i] - d) / 2] == false) isPossible[j] = false;
            }
        }
    }

    vector<int> ans;

    for (int i = 0; i < whichDiffs.size(); ++i)
    {
        if (isPossible[i]) ans.push_back(whichDiffs[i]);
    }

    sort(ans.begin(), ans.end());

    cout << ans.size() << endl;
    for (auto d : ans) cout << d << " ";
    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: 0 / 35