제출 #1142748

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1142748		kitlix	Bootfall (IZhO17_bootfall)	C++20	44 / 100	1004 ms	932 KiB

bootfall

#pragma GCC target("avx2")
#pragma GCC optimize("Ofast,unroll-loops,inline,fast-math")
#include <bits/stdc++.h>

using namespace std;

#ifndef LOCAL
const int MAXN = 500;
const int MAXA = 500;
const int SZ = MAXN * MAXA + 1;
#else
const int MAXN = 20;
const int MAXA = 20;
const int SZ = MAXN * MAXA + 1;
#endif

signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto& el : a)
        cin >> el;
    sort(a.begin(), a.end(), greater<>());
    auto adddp = [&](const bitset<SZ>& bs, int a) {
        bitset<SZ> res;
        res = (bs << a) | (bs >> a);
        int curi = bs._Find_first();
        while (curi < a) {
            res[a - curi] = 1;
            curi = bs._Find_next(curi);
        }
        return res;
        };
    bitset<SZ> cur;
    cur[0] = 1;
    for (int i = 0; i < n; ++i)
        cur = adddp(cur, a[i]);
    if (!cur[0]) {
        cout << 0;
        return 0;
    }
    bitset<SZ> ans;
    ans.set();
    for (int i = 0; i < n; ++i) {
        bitset<SZ> bs;
        bs[0] = 1;
        for (int j = 0; j < n; ++j)
            if (i != j)
                bs = adddp(bs, a[j]);
        ans &= bs;
    }
    vector<int> vars;
    for (int i = 1; i <= MAXN * MAXA; ++i)
        if (ans[i])
            vars.push_back(i);
    cout << vars.size() << '\n';
    for (auto el : vars)
        cout << el << ' ';
}

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