Submission #635753

#	Time	Username	Problem	Language	Result	Execution time	Memory
635753		tvladm2009	Bootfall (IZhO17_bootfall)	C++14	100 / 100	389 ms	5668 KiB

bootfall

#include <iostream>

using namespace std;

const int MAX_N = 500;
const int MOD = 1e9 + 7;
int a[MAX_N + 1], dp[MAX_N * MAX_N + 1], ways[MAX_N * MAX_N + 1], ways2[MAX_N * MAX_N + 1], cnt[MAX_N * MAX_N + 1], aux[MAX_N * MAX_N + 1];
int n;

void addSelf(int &a, int b) {
    a += b;
    if (a >= MOD) {
        a -= MOD;
    }
}

bool hentai(int pos) {
    int s = 0;
    for (int i = 1; i <= n; i++) {
        if (i != pos) {
            s += a[i];
        }
    }
    if (pos == 0) {
        dp[0] = true;
        ways[0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = s; j >= a[i]; j--) {
                dp[j] |= dp[j - a[i]];
                addSelf(ways[j], ways[j - a[i]]);
            }
        }
        if (s % 2 == 0 && dp[s / 2]) {
            return true;
        } else {
            return false;
        }
    } else {
        for (int i = 0; i <= s + a[pos]; i++) {
            ways2[i] = ways[i];
        }
        for (int i = a[pos]; i <= s + a[pos]; i++) {
            addSelf(ways[i], -ways[i - a[pos]]);
        }
        for (int i = 0; i <= s / 2; i++) {
            if (ways[i]) {
                cnt[s - 2 * i]++;
            }
        }
        for (int i = 0; i <= s + a[pos]; i++) {
            aux[i] = ways[i];
        }
        for (int i = 0; i <= s + a[pos]; i++) {
            ways[i] = ways2[i];
        }
        return true;
    }
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    if (!hentai(0)) {
        cout << "0\n";
        return 0;
    }
    for (int i = 1; i <= n; i++) {
        hentai(i);
    }
    int answer = 0;
    for (int i = 0; i <= MAX_N * MAX_N; i++) {
        if (cnt[i] == n) {
            answer++;
        }
    }
    cout << answer << "\n";
    for (int i = 0; i <= MAX_N * MAX_N; i++) {
        if (cnt[i] == n) {
            cout << i << " ";
        }
    }
    return 0;
}

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