Submission #1266343

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266343		Braabebo10	Bootfall (IZhO17_bootfall)	C++20	65 / 100	1008 ms	63304 KiB

bootfall

#include<bits/stdc++.h>
#define ll int
#define nl "\n"
#define all(v) v.begin(),v.end()
#define baraa ios_base::sync_with_stdio(false);cin.tie(NULL);
using namespace std;
const ll mod = 1e9 + 7;
ll add(ll a, ll b) {
    a += b;
    while (a >= mod)a -= mod;
    while (a < 0)a += mod;
    return a;
}

ll mul(ll a, ll b) {
    return (a * b) % mod;
}

int main() {
    baraa
    ll n, M1 = 500 * 500 + 1, M2 = 500 * 500 / 2 + 10;
    cin >> n;
    ll a[n], dp[M2]{};
    bool mem[M2]{};
    ll sm = 0;
    dp[0] = 1;
    for (ll &i: a) {
        cin >> i;
        sm += i;
        for (ll j = M2 - 1; j >= i; j--)
            dp[j] = add(dp[j], dp[j - i]);
    }
    if (sm % 2 or dp[sm / 2] == 0) {
        cout << 0 << nl;
        return 0;
    }
    bool save[n][M2];
    for (ll i = 0; i < n; i++) {
        for (ll j = a[i]; j < M2; j++)
            dp[j] = add(dp[j], -dp[j - a[i]]);

        for (ll j = 0; j < M2; j++)
            mem[j] = (dp[j] > 0), save[i][j] = mem[j];


        for (ll j = M2 - 1; j >= a[i]; j--)
            dp[j] = add(dp[j], dp[j - a[i]]);
    }
    vector<ll> ans;
    for (ll x = 1; x < M1; x++) {
        bool ok = 1;
        for (ll i = 0; i < n and ok; i++) {
            ll sm2 = (sm - a[i] + x);
            ok &= (sm2 / 2 - x >= 0 and (sm2 / 2) * 2 == sm2 and save[i][min(sm2 / 2, sm2 / 2 - x)]);
        }
        if (ok)ans.push_back(x);
    }
    cout << ans.size() << nl;
    for (ll i: ans) {
        cout << i << ' ';
    }
    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