Submission #1293666

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293666		domi	Bootfall (IZhO17_bootfall)	C++20	13 / 100	1095 ms	588 KiB

bootfall

#include <bits/stdc++.h>

#define int long long
#define fi first
#define se second

#define sz(a) (int)((a).size())
#define all(a) (a).begin(), (a).end()

#define lsb(x) (x & (-x))
#define vi vector<int>
#define YES { cout << "YES" << endl; return; }
#define NO { cout << "NO" << endl; return; }

using ll = long long;
using pii = std::pair<int, int>;

const int NMAX = 5e2;
const int GMAX = 25e4;

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int s;

struct Knapsack {
    int dp[GMAX + 5];
    int MOD;

    Knapsack() {
        MOD = rng();
        dp[0] = 1;
    }

    void add(int x) {
        for (int i = s; i >= x; --i)
            dp[i] = (dp[i] + dp[i - x]) % MOD;
    }

    void remove(int x) {
        for (int i = x; i <= s; ++i)
            dp[i] = (dp[i] - dp[i - x] + MOD) % MOD;
    }
};

Knapsack rucsac;
int a[NMAX + 5], n;

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n;

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

    for (int i = 1; i <= n; ++i)
        rucsac.add(a[i]);

    if (s % 2 == 1 || rucsac.dp[s / 2] == 0) {
        cout << "0\n";
        exit(0);
    }

    vector<int>ans;
    for (int t = 1; t <= 2 * s; ++t) {
        a[n + 1] = t;
        rucsac.add(a[n + 1]);

        bool ok = true;
        for (int i = 1; i <= n + 1 && ok; ++i) {
            rucsac.remove(a[i]);
            int cur_sum = s + t - a[i];

            if (cur_sum % 2 != 0 || rucsac.dp[cur_sum / 2] == 0)
                ok = false;

            rucsac.add(a[i]);
        }

        if (ok)
            ans.push_back(t);

        rucsac.remove(a[n + 1]);
    }

    cout << sz(ans) << '\n';
    for (auto &it : ans)
        cout << it << " \n"[it == ans.back()];
    return 0;
}

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