제출 #1257289

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1257289		proofy	Bootfall (IZhO17_bootfall)	C++20	65 / 100	1094 ms	1240 KiB

bootfall

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const int N = 501;
bitset<N * N> st;

int freq[N * N];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

    int n;
    cin >> n;
    vector<int> a(n);
    for (int& u : a) cin >> u;

    st.reset();
    st[0] = 1;
    for (int i = 0; i < n; i++) st = (st << a[i]) | st;

    int sum = 0;
    for (int& u : a) sum += u;

    if (sum % 2 != 0) return cout << 0, 0;
    if (st[sum / 2] == 0) return cout << 0, 0;

    for (int i = 0; i < n; i++) {
        st = bitset<N * N>();
        st[0] = 1;
        int S = 0;
        for (int j = 0; j < n; j++) if (j != i) {
            st = (st << a[j]) | st;
            S += a[j];
        }
        freq[S] += 1;
        for (int j = 1; j <= S - j && j < S; j++) if (st[j]) {
            assert(st[S - j]);
            freq[S - 2 * j] += 1;
        }
    }

    int count_ans = 0;
    for (int j = 0; j <= sum; j++) count_ans += (freq[j] == n);

    cout << count_ans << "\n";
    for (int j = 0; j <= sum; j++) if (freq[j] == n)
        cout << j << " ";
    cout << "\n";
}

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