제출 #1273405

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1273405		bbldrizzy	Bootfall (IZhO17_bootfall)	C++20	28 / 100	324 ms	267352 KiB

bootfall

#include <bits/stdc++.h>
#include <ios>
#include <iostream>
#include <set>
#include <random>
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
#define f first
#define s second
const int MOD = 1e9+7;
const ll inf = 4*1e18;
const int mx = 5*1e5+5;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
const int N = 500*500 + 5;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int n; cin >> n;
    vector<int> a(n);
    int odd = 0; int even = 0;
    int sum = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        if (a[i] % 2) {
            odd++;
        } else { even++; }
        sum += a[i];
    }
    if ((even > 0 && odd > 0) || sum%2 == 1) {
        cout << 0; exit(0);
    }
    sort(a.begin(), a.end());
    vector<int> dp(N, 0);
    dp[0] = 1;
    for (int i = 0; i < n; i++) {
        for (int j = N-1; j >= a[i]; j--) {
            dp[j] = (dp[j] + dp[j-a[i]]) % MOD;
        }
    }
    if (dp[sum/2] == 0) {
        cout << 0; exit(0);
    }
    vector<vector<int>> dp2(n, vector<int>(N, 0));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < N; j++) {
            dp2[i][j] = (dp2[i][j]+dp[j] - (j-a[i] >= 0 ? dp2[i][j-a[i]] : 0) + MOD)%MOD;
        }
    }
    vector<int> ans;
    for (int i = 1; i <= 500*500; i++) {
        if (i%2 != a[0]%2) continue;
        bool pos = true;
        for (int j = 0; j < n; j++) {
            int tmp = sum - a[j];
            tmp += i;
            tmp /= 2;
            if (!(dp2[j][tmp]>0 || (i < tmp && dp2[j][tmp-i]>0))) {
                pos = false;
                break;
            }
        }
        if (pos) {
            ans.push_back(i);
        }
    }
    cout << ans.size() << "\n";
    for (int i : ans) cout << i << " ";
    // vector<bitset<N>> dp(n);
    // for (int i = 0; i < n; i++) {
    //     if (i > 0 && a[i] == a[i-1]) {
    //         dp[i] = dp[i-1];
    //         continue;
    //     }
    //     dp[i].set(0);
    //     for (int j = 0; j < n; j++) {
    //         if (j == i) continue;
    //         dp[i] = dp[i] | (dp[i] << a[j]);
    //     }
    // }
    // bool og = false;
    // for (int i = 0; i < n; i++) {
    //     if (dp[i][sum/2]) og = true;    
    // }
    // if (!og) {
    //     cout << 0; exit(0);
    // }
    // vector<int> ans;
    // for (int i = 1; i <= 500*500; i++) {
    //     if (i%2 != a[0]%2) continue;
    //     bool pos = true;
    //     for (int j = 0; j < n; j++) {
    //         int tmp = sum - a[j];
    //         tmp += i;
    //         tmp /= 2;
    //         if (!(dp[j][tmp] || (i < tmp && dp[j][tmp-i]))) {
    //             pos = false;
    //             break;
    //         }
    //     }
    //     if (pos) {
    //         ans.push_back(i);
    //     }
    // }
    // cout << ans.size() << "\n";
    // for (int i : ans) cout << i << " ";
}

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