Submission #1207936

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207936		borisAngelov	Bootfall (IZhO17_bootfall)	C++20	100 / 100	129 ms	19088 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];
bitset<MAX> dpWithout[maxn];

void dnc(int l, int r, bitset<MAX> curr)
{
    if (l == r)
    {
        dpWithout[l] = curr;
        return;
    }

    int mid = (l + r) / 2;

    bitset<MAX> dpL = curr;
    for (int i = l; i <= mid; ++i)
    {
        dpL |= (dpL << a[i]);
    }
    dnc(mid + 1, r, dpL);

    bitset<MAX> dpR = curr;
    for (int i = mid + 1; i <= r; ++i)
    {
        dpR |= (dpR << a[i]);
    }
    dnc(l, mid, dpR);
}

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;
    }

    dp.reset();
    dp[0] = 1;

    dnc(1, n, dp);

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

    for (int i = 1; i <= n; ++i)
    {
        dp = dpWithout[i];

        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: 35 / 35