Submission #994282

#TimeUsernameProblemLanguageResultExecution timeMemory
994282VMaksimoski008Bootfall (IZhO17_bootfall)C++17
65 / 100
1076 ms15988 KiB
#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;

bitset<S> bs[501];

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

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

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

    if(sum % 2 == 1 || !bs[0][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]);
        // cout << i << ": ";
        // for(int j=0; j<=10; j++) if(bs[i+1][j]) cout << j << " ";
        // cout << '\n';
    }

    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;
            if( (bs[i][(sum - v[i-1] + j) / 2]) == 0 ) ok = 0;
        }
        if(ok) ans.push_back(j);
    }

    cout << ans.size() << '\n';
    for(int &x : ans) cout << x << " ";
    return 0;
}
#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...