Submission #994276

#	Time	Username	Problem	Language	Result	Execution time	Memory
994276		VMaksimoski008	Bootfall (IZhO17_bootfall)	C++17	65 / 100	1072 ms	16016 KiB

bootfall

#include <bits/stdc++.h>

#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
//#define int long long

using namespace std;

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

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int mod = 1e9 + 7;
const int LOG = 20;
const int maxn = 1e5 + 5;
const double eps = 1e-9;
const int S = (500 * 500) + 1;

bitset<S> bs[501];

int32_t 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<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;
}

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