Submission #1142750

#TimeUsernameProblemLanguageResultExecution timeMemory
1142750kitlixBootfall (IZhO17_bootfall)C++20
44 / 100
1024 ms936 KiB
#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

mt19937 gen(chrono::duration_cast<chrono::milliseconds>(chrono::system_clock::now().time_since_epoch()).count());

template <typename T>
void shuffle(vector<T>& a) {
    for (int i = 0; i < a.size(); ++i)
        swap(a[i], a[gen() % (i + 1)]);
}

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;
    shuffle(a);
    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 << ' ';
}


#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...