Submission #170497

#	Time	Username	Problem	Language	Result	Execution time	Memory
170497		mcdx9524	Bootfall (IZhO17_bootfall)	C++14	100 / 100	956 ms	3828 KiB

bootfall

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 500 * 500 + 7;
const int mod = 1e9 + 7;

int dp[N];
int can[N];

void add(int x) {
    for (int i = N - x - 1; i >= 0; i--) {
        dp[i + x] = (dp[i + x] + dp[i]) % mod;
    }
}

void rem(int x) {
    for (int i = x; i < N; i++) {
        dp[i] = (dp[i] - dp[i - x] + mod) % mod;
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector <int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    dp[0] = 1;
    int sum = 0;
    for (int i = 0; i < n; i++) {
        add(a[i]);
        sum += a[i];
    }
    if (!dp[sum / 2]) {
        cout << 0 << '\n';
        return 0;
    }
    for (int i = 0; i < n; i++) {
        sum -= a[i];
        rem(a[i]);
        for (int j = 0; j < N; j++) {
            if (dp[j]) {
                can[abs(sum - 2 * j)]++;
            }
        }
        sum += a[i];
        add(a[i]);
    }
    vector <int> res;
    for (int i = 1; i < N; i++) {
        if (can[i] == 2 * n) {
            res.push_back(i);
        }
    }
    cout << (int) res.size() << '\n';
    for (int x : res) {
        cout << x << ' ';
    }
    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