제출 #1257290

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

bootfall

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

const int mod = 1e9 + 7;
int mul(int a, int b) { return (a * 1LL * b) % mod; }
int add(int a, int b) { return (a + b) % mod; }
int sub(int a, int b) { return (a - b + mod) % mod; }

const int N = 501;
int st[N * N]; // number of subsets that sum up to a certain value
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;

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

    if (sum % 2 != 0) return cout << "0\n", 0;

    auto add_contribution = [&](int x) {
        for (int j = sum - x; j >= 0; --j) st[j + x] = add(st[j + x], st[j]);
    };

    auto remove_contribution = [&](int x) {
        for (int j = 0; j <= sum - x; j++) st[j + x] = sub(st[j + x], st[j]);
    };

    st[0] = 1;
    for (int i = 0; i < n; i++) {
        add_contribution(a[i]);
    }

    if (st[sum / 2] == 0) return cout << "0\n", 0;
    
    for (int i = 0; i < n; i++) {
        remove_contribution(a[i]);

        int S = 0;
        for (int j = 0; j < n; j++) if (j != i) 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;
        }

        add_contribution(a[i]);
    }

    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: 35 / 35