Submission #1232930

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232930		Bahamin	Bootfall (IZhO17_bootfall)	C++20	100 / 100	169 ms	32856 KiB

bootfall

#include <bits/stdc++.h>

using namespace std;

template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }

#define ll long long
#define ld long double
#define all(a) (a).begin(), (a).end()
#define sui cout.tie(NULL); cin.tie(NULL); ios_base::sync_with_stdio(false)
const int MAX_N = 501;
const int MAX_MUL = 500 * 500 + 1;
const int MOD = 1e9 + 7;
const ll INF = 1e9;
const ld EPS = 1e-9;
const int LOG = 30;

bitset<MAX_MUL> dp[MAX_N << 2];
int id1[MAX_N];
int a[MAX_N];
int n;
bitset<MAX_MUL> now;
bitset<MAX_MUL> temp;

void f(int l, int r, int id)
{
    dp[id] = now;
    if (l == r - 1)
    {
        id1[l] = id;
        return;
    }
    int mid = (r + l) >> 1;
    for (int i = mid; i < r; i++) now |= (now << a[i]);
    f(l, mid, id * 2);
    now = dp[id];
    for (int i = l; i < mid; i++) now |= (now << a[i]);
    f(mid, r, id * 2 + 1);
    now = dp[id];
}

void solve() {
    cin >> n;
    int sum = 0;
    for (int i = 0; i < n; i++) cin >> a[i], sum += a[i];
    now.set(0);
    f(0, n, 1);
    if (sum % 2 || !(dp[id1[0]] | (dp[id1[0]] << a[0]))[sum / 2])
    {
        cout << 0 << endl;
        return;
    }
    vector<int> ans;
    for (int i = 1; i < MAX_MUL; i++)
    {
        bool ok = true;
        for (int j = 0; j < n; j++) if (a[j] % 2 != i % 2 || sum < i + a[j] || !dp[id1[j]][(sum - i - a[j]) / 2]) 
        {
            ok = false;
            break;
        }
        if (ok) ans.push_back(i);
    }
    cout << ans.size() << "\n";
    for (int x : ans) cout << x << " ";
    cout << "\n";
}

int main() {
    sui;
    int tc = 1;
    //cin >> tc;
    for (int t = 1; t <= tc; t++) {
        solve();
    }
}

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