Submission #835710

#	Time	Username	Problem	Language	Result	Execution time	Memory
835710		vjudge1	Bootfall (IZhO17_bootfall)	C++17	100 / 100	343 ms	4320 KiB

bootfall

#include <bits/stdc++.h>
using namespace std;

/// 123
int32_t main() {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; i++) cin >> a[i];
        int sum = accumulate(a.begin(), a.end(), 0);
        vector<int64_t> f(sum + 1, 0);
        f[0] = 1;
        for (int i = 0; i < n; i++) {
                for (int j = sum; j >= a[i]; j--) {
                        f[j] += f[j - a[i]];
                }
        }

        if (sum % 2 || f[sum / 2] == 0) {
                return cout << 0, 0;
        }
        vector<int> good(sum + 1, 1);

        for (int i = 0; i < n; i++) {
                for (int j = a[i]; j <= sum; j++) {
                        f[j] -= f[j - a[i]];
                }
                for (int j = 0; j <= sum; j++) {
                        good[j] &= ((j + sum - a[i]) % 2 == 0) && (f[(j + sum - a[i]) / 2]);
                }
                for (int j = sum; j >= a[i]; j--) {
                        f[j] += f[j - a[i]];
                }
        }

        vector<int> ans;
        for (int i = 1; i <= sum; i++) {
                if (good[i]) ans.emplace_back(i);
        }
        cout << ans.size() << '\n';
        for (int i : ans) cout << i << ' ';
}

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