Submission #1273401

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273401		bbldrizzy	Bootfall (IZhO17_bootfall)	C++20	65 / 100	1036 ms	16964 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<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: 16 / 16
• Subtask 5: 21 / 21
• Subtask 6: 0 / 35