제출 #507087

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
507087		syl123456	Bootfall (IZhO17_bootfall)	C++17	100 / 100	285 ms	3300 KiB

bootfall

#pragma GCC diagnostic ignored "-Wunused-parameter"
#pragma GCC diagnostic ignored "-Wunused-variable"
#pragma GCC diagnostic ignored "-Wparentheses"
#include <bits/stdc++.h>
#define all(i) (i).begin(), (i).end()
#define random random_device rd; mt19937 rng(rd())
using namespace std;
template<typename T1, typename T2>
ostream& operator << (ostream &i, pair<T1, T2> j) {
    return i << j.first << ' ' << j.second;
}
template<typename T>
ostream& operator << (ostream &i, vector<T> j) {
    i << '{' << j.size() << ':';
    for (T ii : j) i << ' ' << ii;
    return i << '}';
}
void Debug(bool _split) {}
template<typename T1, typename ...T2>
void Debug(bool _split, T1 x, T2 ...args) {
    if (_split)
        cerr << ", ";
    cerr << x, Debug(true, args...);
}
template<typename T>
void Debuga(T *i, int n) {
    cerr << '[';
    for (int j = 0; j < n; ++j) cerr << i[j] << " ]"[j == n - 1];
    cerr << endl;
}
#ifdef SYL
#define debug(args...) cerr << "\u001b[35mLine(" << __LINE__ << ") -> [" << #args << "] is [", Debug(false, args), cerr << "]\u001b[0m" << endl
#define debuga(i) cerr << "\u001b[35mLine(" << __LINE__ << ") -> [" << #i << "] is ", Debuga(i, sizeof(i) / sizeof(typeid(*i).name())), cerr << "\u001b[0m"
#else
#define debug(args...) void(0)
#define debuga(i) void(0)
#endif
typedef long long ll;
typedef pair<int, int> pi;
const int inf = 0x3f3f3f3f, lg = 20;
const ll mod = 1e9 + 7, INF = 0x3f3f3f3f3f3f3f3f;

const int N = 500, C = N * (2 * N + 1), zro = N * N;
bitset<C> is[11][2];
bool ok[C];
int a[N];

void calc(int l, int r, int dep) {
    is[dep + 1][0] = is[dep][0];
    int nxt = 1, pre = 0;
    while (l < r) {
        is[dep + 1][nxt] = is[dep + 1][pre] << a[l];
        is[dep + 1][nxt] |= is[dep + 1][pre] >> a[l];
        swap(nxt, pre);
        ++l;
    }
    if (pre)
        is[dep + 1][0] = is[dep + 1][1];
}

void dc(int l, int r, int dep) {
    if (l == r - 1) {
        for (int i = zro + 1; i < C; ++i)
            ok[i] = ok[i] & is[dep][0].test(i);
        return;
    }
    int m = l + r >> 1;
    calc(l, m, dep);
    dc(m, r, dep + 1);
    calc(m, r, dep);
    dc(l, m, dep + 1);
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    fill(ok, ok + C, true);
    is[0][0].set(zro, true);
    dc(0, n, 0);
    calc(0, n, 0);
    if (!is[1][0].test(zro))
        return cout << 0, 0;
    vector<int> ans;
    for (int i = zro + 1; i < C; ++i)
        if (ok[i])
            ans.push_back(i - zro);
    cout << ans.size() << '\n';
    for (int i : ans)
        cout << i << ' ';
}
/*
n^2C pre,suf

k * (n^2C + n/k * n/k * nC)

T(N) = 2 * (N/2 * maxN * C + T(N/2))
     = 2T(N/2) + NmaxNC
n maxn c lgn
*/

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