Submission #172965

#	Time	Username	Problem	Language	Result	Execution time	Memory
172965		VEGAnn	Bootfall (IZhO17_bootfall)	C++14	100 / 100	725 ms	4096 KiB

bootfall

#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define PB push_back
#define all(x) x.begin(),x.end()
using namespace std;
const int N = 510;
const int N2 = N * N;
const int PW = 10;
const int VL = (1 << PW);
const int oo = 2e9;
const int K = 11;
const int md = int(1e9) + 7;
vector<int> ans, nw;
int f[N2], a[N], n, pref;

int sum(int x, int y){ return (x + y) % md; }

void BAD(){
    cout << 0;
    exit(0);
}

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

    cin >> n;

    f[0] = 1;

    for (int i = 0; i < n; i++) {
        cin >> a[i];

        pref += a[i];

        for (int j = pref; j >= a[i]; j--)
            f[j] = sum(f[j], f[j - a[i]]);
    }

    if (pref & 1) BAD();
    if (f[pref >> 1] == 0) BAD();

    ans.clear();
    for (int i = 1; i < N2; i++)
        ans.PB(i);

    for (int i = 0; i < n; i++){
        for (int j = a[i]; j <= pref; j++)
            f[j] = sum(f[j], md - f[j - a[i]]);

        nw.clear();
        for (int x : ans){
            int sm = pref - a[i] + x;
            if (sm & 1) continue;
            if (f[sm >> 1] == 0) continue;
            nw.PB(x);
        }

        ans = nw;

        for (int j = pref; j >= a[i]; j--)
            f[j] = sum(f[j], f[j - a[i]]);
    }

    cout << sz(ans) << '\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: 35 / 35