Submission #994287

#	Time	Username	Problem	Language	Result	Execution time	Memory
994287		VMaksimoski008	Bootfall (IZhO17_bootfall)	C++17	65 / 100	1056 ms	16972 KiB

bootfall

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,bmi,bmi2,lzcnt,popcnt")

const int S = (500 * 500) + 1;
const int S2 = (500 * 500) / 2 + 1;

bitset<S> bs[501];
bitset<S2> bs2;

int main() {
    ios_base::sync_with_stdio(false);
    cout.tie(0); cin.tie(0);

    int n, sum = 0;
    cin >> n;

    vector<int> v(n);
    bs2[0] = 1;
    for(int &x : v) {
        cin >> x;
        sum += x;
        bs2 |= (bs2 << x);
    }

    if(sum % 2 == 1 || !bs2[sum/2]) {
        cout << 0 << '\n';
        return 0;
    }

    for(int i=0; i<n; i++) {
        bs[i+1][0] = 1;
        for(int j=0; j<n; j++)
            if(i != j) bs[i+1] |= (bs[i+1] << v[j]);
    }

    vector<int> ans;

    for(int j=1; j<min(sum, S); j++) {
        bool ok = 1;
        for(int i=1; i<=n; i++) {
            if( (sum - v[i-1] + j) % 2 == 1 ) {
                ok = 0;
                break;
            }

            if( (bs[i][(sum - v[i-1] + j) / 2]) == 0) {
                ok = 0;
                break;
            }
        }
        if(ok) ans.push_back(j);
    }

    cout << ans.size() << '\n';
    for(int &x : ans) cout << x << " ";
    return 0;
}

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