Submission #1271230

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271230		LucasLe	Bootfall (IZhO17_bootfall)	C++20	100 / 100	201 ms	5748 KiB

bootfall

#include <bits/stdc++.h>

#define fi first
#define se second
#define ld long double
#define pii std::pair<int, int>
#define piii std::pair<pii, pii>

#define rep(i,a) for (int i = 0; i < a; ++i)
#define per(i,a) for (int i = a - 1; i >= 0; --i)

int N;
int sum;
int a[505];

long long dp[250001], f[250001];
int cnt[250001];

void solve() {
    std::cin >> N;
    for (int i = 1; i <= N; ++i) {
        std::cin >> a[i];
        sum += a[i];
    }

    if (N == 1) {
        std::cout << 0 << '\n';
        return;
    }

    dp[0] = 1;
    for (int i = 1; i <= N; ++i) {
        for (int j = sum; j >= a[i]; --j)
            dp[j] += dp[j - a[i]];
    }

    if ((sum & 1) || !dp[sum / 2]) {
        std::cout << 0 << '\n';
        return;
    }

    f[0] = 1;
    for (int i = 1; i <= N; ++i) {
        for (int x = 0; x <= sum; ++x) {
            f[x] = dp[x];
            if (x >= a[i])
                f[x] -= f[x - a[i]];
            if (f[x]) {
                int val = x * 2 + a[i] - sum;
                if (val >= 1 && val <= sum)
                    cnt[val]++;
            }
        }
    }

    int ans = 0;
    for (int i = 1; i <= sum; ++i)
        if (cnt[i] == N) ans++;

    std::cout << ans << '\n';
    for (int i = 1; i <= sum; ++i)
        if (cnt[i] == N)
            std::cout << i << ' ';
}

int main() {
    // std::freopen("input.txt", "r", stdin);
    // std::freopen("palin.inp", "r", stdin);
    // std::freopen("sushi.out", "w", stdout);
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(0);

    int T = 1;
    // std::cin >> T;
    while (T--)
        solve();

}

// 14 / 2 (87.5% Rate)

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