제출 #1270722

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1270722		LucasLe	Bootfall (IZhO17_bootfall)	C++20	28 / 100	1016 ms	17352 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];
std::bitset<500001> dp[502];

void solve() {
    std::cin >> N;

    for (int i = 1; i <= N + 1; ++i)
        dp[i][0] = 1;

    bool odd = false, even = false;
    for (int i = 1; i <= N; ++i) {
        std::cin >> a[i];
        sum += a[i];
        if (a[i] & 1)
            odd = true;
        else
            even = true;
    }

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

    for (int i = 1; i <= N + 1; ++i) {
        for (int j = 1; j <= N; ++j) if (i != j) {
            int val = 2 * a[j];
            dp[i] |= (dp[i] << val);
        }
    }

    if ((sum & 1) || !dp[N + 1][sum] || (odd && even)) {
        std::cout << 0 << '\n';
        return;
    }

    dp[N + 1] = (dp[1] << a[1]);
    for (int i = 2; i <= N; ++i)
        dp[N + 1] &= (dp[i] << a[i]);

    int x = 1, ans = 0;
    std::vector<int> res;

    if ((sum + x - a[1]) & 1) x = 2;
    for (; x <= sum; x += 2) {
        if (dp[N + 1][sum + x]) {
            ans++;
            res.push_back(x);
        }
    }

    std::cout << ans << '\n';
    for (int x : res)
        std::cout << x << ' ';
}

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: 0 / 16
• Subtask 5: 0 / 21
• Subtask 6: 0 / 35