Submission #1273406

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273406		bbldrizzy	Bootfall (IZhO17_bootfall)	C++20	100 / 100	479 ms	3400 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);
    }
    bitset<N> ans;
    for (int i = 0; i < N; i++) {
        ans.set(i);
    }
    for (int i = 0; i < n; i++) {
        vector<int> dp2(N, 0);
        bitset<N> can;
        for (int j = 0; j < N; j++) { 
            dp2[j] = (dp2[j]+dp[j] - (j-a[i] >= 0 ? dp2[j-a[i]] : 0) + MOD)%MOD; 
        }
        for (int j = 1; j < N; j++) {
            if (j%2 != a[0]%2) continue;
            int tmp = sum - a[i];
            tmp += j;
            tmp /= 2;
            if (dp2[tmp] || (j < tmp && dp2[tmp-j])) {
                can.set(j);
            }
        }
        ans &= can;
    }   
    vector<int> res;
    for (int i = 1; i <= 500*500; i++) {
        if (ans[i]) res.push_back(i);
    }
    cout << res.size() << "\n";
    for (int i : res) 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: 16 / 16
• Subtask 5: 21 / 21
• Subtask 6: 35 / 35