제출 #331700

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
331700		vitkishloh228	Bootfall (IZhO17_bootfall)	C++14	100 / 100	285 ms	3172 KiB

bootfall

#include<iostream>
#include<vector>
#include<algorithm>
#include<bitset>
using namespace std;
const int maxc = 500 * 500 + 10;
int S;
bitset<maxc> ans, q;
vector<int> a;
void solve(int l,int r,bitset<maxc> b) {
    if (l == r) {
        q.reset();
        for (int j = 0; j < maxc; ++j) {
            int needsum = (S - 2 * j - a[l]);
            if (needsum < 0) continue;
            if (b[j]) {
                q[needsum] = 1;
            }
        }
        ans &= q;
        return;
    }
    int m = (l + r) >> 1;
    bitset<maxc> l1, r1;
    l1 = b;
    r1 = b;
    for (int i = l; i <= m; ++i) {
        l1 |= l1 << a[i];
    }
    for (int i = m + 1; i <= r; ++i) {
        r1 |= r1 << a[i];
    }
    solve(l, m, r1);
    solve(m + 1, r, l1);
}
int main() {
    int n;
    cin >> n;
    a.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        S += a[i];
    }
    for (int i = 0; i < maxc; ++i) ans[i] = 1;
    bitset<maxc> cur;
    cur[0] = 1;
    solve(0, n - 1, cur);
    for (int i = 0; i < n; ++i) {
        cur |= cur << a[i];
    }
    if (S % 2 || !cur[S / 2]) {
        cout << 0;
        return 0;
    }
    vector<int> answer;
    for (int i = 1; i < maxc; ++i) {
        if (ans[i]) answer.push_back(i);
    }
    cout << answer.size() << '\n';
    for (auto elem : answer) cout << elem << ' ';
}

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