Submission #1207054

#TimeUsernameProblemLanguageResultExecution timeMemory
1207054borisAngelovBootfall (IZhO17_bootfall)C++20
65 / 100
1044 ms1260 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...