제출 #1347222

#제출 시각아이디문제언어결과실행 시간메모리
1347222i_love_kim_ji_wonBootfall (IZhO17_bootfall)C++20
0 / 100
0 ms344 KiB
// I ♡ 鞠婧祎
// #pragma GCC optimize("Ofast")
// #pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#define freopen(name) if(fopen(name".INP","r")) {freopen (name".INP","r",stdin); freopen (name".OUT","w",stdout);}
using namespace std;

using ll = long long;

void justDoIt();

int main() {
    // freopen("");
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    justDoIt();
    return 0;
}

const int N = 505;

int a[N];
int dp[N * N], f[N * N];
bool used[N];
const int mod = 1e9 + 7;
int sum = 0;

void add(int x) {
    for (int j = sum; j >= 0; j--) {
        dp[j + x] += dp[j];
        if (dp[j + x] >= mod) {dp[j + x] -= mod;}
    }
    sum += x;
}

void del(int x) {
    sum -= x;
    for (int j = 0; j <= sum; j++) {
        dp[j + x] += (mod - dp[j]);
        if (dp[j + x] >= mod) {dp[j + x] -= mod;}
    }
}

void test() {
    int n;
    cin >> n;
    bool odd = 0, even = 0;
    int s = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        s += a[i];
        if (a[i] & 1) {odd = 1;}
        else {even = 1;}
    }
    if (odd && even) {cout << 0; return;}
    dp[0] = 1;
    for (int i = 1; i <= n; i++) {
        add(a[i]);
    }
    for (int i = 1; i <= n; i++) {
        if (used[a[i]]) {continue;}
        used[a[i]] = 1;
        del(a[i]);
        for (int j = 1; j <= s; j++) {
            int cur = s - a[i] + j;
            if (cur & 1 || !dp[cur / 2]) {
                f[j] = 1;
            }
        }
        add(a[i]);
    }
    vector<int> v;
    for (int i = 1; i <= s; i++) {
        if (!f[i]) {
            v.push_back(i);
        }
    }
    cout << v.size() << '\n';
    for (auto it : v) {
        cout << it << ' ';
    }
}

void justDoIt() {
    int t = 1;
    // cin >> t;
    for (int tests = 1; tests <= t; tests++) {
        test();
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...