Submission #156211

#	Time	Username	Problem	Language	Result	Execution time	Memory
156211		theboatman	Bootfall (IZhO17_bootfall)	C++17	13 / 100	1067 ms	36916 KiB

bootfall

#include <bits/stdc++.h>

#define y1 theboatman
#define make_struct(args...) {args}

using namespace std;

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

    int n;
    cin >> n;

    int sum = 0;
    vector <int> a(n + 1);

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

    vector <vector <int> > dp_pref(n + 1, vector <int> (sum * 2 + 1));
    dp_pref[0][sum] = 1;

    vector <set <int> > pref(n + 1);
    pref[0].insert(sum);

    for(int i = 1; i <= n; i++) {
        for(int bal = 0; bal <= sum * 2; bal++) {
            if (dp_pref[i - 1][bal]) {
                dp_pref[i][bal + a[i]] = 1;
                dp_pref[i][bal - a[i]] = 1;
            }
        }

        for(int bal = 0; bal <= sum * 2; bal++) {
            if (dp_pref[i][bal]) {
                pref[i].insert(bal);
            }
        }
    }

    vector <vector <int> > dp_suff(n + 2, vector <int> (sum * 2 + 1));
    dp_suff[n + 1][sum] = 1;

    vector <set <int> > suff(n + 2);
    suff[n + 1].insert(sum);

    for(int i = n; i > 0; i--) {
        for(int bal = 0; bal <= sum * 2; bal++) {
            if (dp_suff[i + 1][bal]) {
                dp_suff[i][bal + a[i]] = 1;
                dp_suff[i][bal - a[i]] = 1;
            }
        }

        for(int bal = 0; bal <= sum * 2; bal++) {
            if (dp_suff[i][bal]) {
                suff[i].insert(bal);
            }
        }
    }

    vector <int> ans;
    for(int power = 1; power <= sum; power++) {
        int ok = 0;

        if (!dp_pref[n][sum]) {
            ok = -1;
        }

        for(int i = 1; i <= n; i++) {
            for(auto it : pref[i - 1]) {
                //cout << it << endl;
                if (suff[i + 1].find(2 * sum - it - power) != suff[i + 1].end()) {
                    ok++;
                    break;
                }
            }

            if (ok != i) {
                break;
            }
        }

        if (ok == n) {
            ans.push_back(power);
        }
    }

    cout << ans.size() << "\n";
    for(auto i : ans) {
        cout << i << " ";
    }
    return 0;
}
/*
x + power + y - sum == 0

y == sum - x - power

1001
999
*/

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