Submission #1142690

#	Time	Username	Problem	Language	Result	Execution time	Memory
1142690		kitlix	Bootfall (IZhO17_bootfall)	C++20	28 / 100	547 ms	692 KiB

bootfall

#include <bits/stdc++.h>

using namespace std;

#ifndef LOCAL
const int MAXN = 100;
const int MAXA = 100;
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;
    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;
        };
    vector<bitset<SZ>> suffdp(n + 1);
    suffdp[n][0] = 1;
    for (int i = n - 1; i >= 0; --i)
        suffdp[i] = adddp(suffdp[i + 1], a[i]);
    if (!suffdp[0][0]) {
        cout << 0;
        return 0;
    }
    bitset<SZ> ans;
    ans.set();
    bitset<SZ> cur;
    cur[0] = 1;
    for (int i = 0; i < n; ++i) {
        auto& left = cur;
        auto& right = suffdp[i + 1];
        bitset<SZ> temp;
        int curi = left._Find_first();
        while (curi != SZ) {
            temp |= (right << curi);
            temp |= (right >> curi);
            curi = left._Find_next(curi);
        }
        curi = right._Find_first();
        while (curi != SZ) {
            temp |= (left << curi);
            temp |= (left >> curi);
            curi = right._Find_next(curi);
        }
        ans &= temp;
        cur = adddp(cur, a[i]);
    }
    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: 0 / 16
• Subtask 5: 0 / 21
• Subtask 6: 0 / 35