Submission #211306

#	Time	Username	Problem	Language	Result	Execution time	Memory
211306		a14789654	Bootfall (IZhO17_bootfall)	C++17	100 / 100	367 ms	3568 KiB

bootfall

#include <bits/stdc++.h>

using namespace std;

const int maxn = 507;

int D[maxn * maxn], a[maxn];

int main()
{
//    freopen("TEST.INP", "r", stdin);
//    freopen("TEST.OUT", "w", stdout);
    int n, sum = 0;
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> a[i], sum += a[i];

    D[0] = 1;
    for (int i = 1; i <= n; ++i)
        for (int j = sum / 2; j >= 0; --j)
            D[j + a[i]] += D[j];

    if ((sum & 1) || !D[sum / 2]) return cout << 0, 0;

    vector <int> cnt(sum + 1);
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 0; j <= sum; ++j)
            D[j + a[i]] -= D[j];

        for (int j = 1; j <= sum; ++j)
        {
            int val = sum - a[i] + j;
            cnt[j] += (val / 2 - j >= 0 && 1 - val % 2 && D[val / 2 - j]);
        }

        for (int j = sum / 2; j >= 0; --j)
            D[j + a[i]] += D[j];
    }

    vector <int> ans;
    for (int i = 1; i <= sum; ++i)
        if (cnt[i] == n) ans.push_back(i);

    cout << (int)ans.size() << '\n';
    for (int x: ans) cout << x << ' ';
    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