Submission #1293673

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293673		domi	Bootfall (IZhO17_bootfall)	C++20	65 / 100	1095 ms	3648 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 = 8e5;

using namespace std;

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

int s;

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

    Knapsack() {
        MOD = 1e9 + 7;
        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], cnt[GMAX + 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);
    }

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

        for (int t = 1; t <= 2 * s; ++t) {
            int total = s + t - a[i];

            if (total % 2 == 0) {
                int need = total / 2;
                int x = need - t;
                if (x >= 0 && rucsac.dp[x] != 0)
                    ++cnt[t];
            }
        }
        rucsac.add(a[i]);
    }

    vector<int>ans;
    for (int t = 1; t <= 2 * s; ++t)
        if (cnt[t] == n)
            ans.push_back(t);

    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: 15 / 15
• Subtask 4: 16 / 16
• Subtask 5: 21 / 21
• Subtask 6: 0 / 35