제출 #1257289

#제출 시각아이디문제언어결과실행 시간메모리
1257289proofyBootfall (IZhO17_bootfall)C++20
65 / 100
1094 ms1240 KiB
#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";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...