제출 #1270430

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1270430		dang_hai_long	Bootfall (IZhO17_bootfall)	C++20	0 / 100	1 ms	320 KiB

bootfall

#include <bits/stdc++.h>

using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    if (!(cin >> N)) return 0;
    vector<int> a(N+1);
    int maxa = 0;
    long long S = 0;
    for (int i = 1; i <= N; ++i){
        cin >> a[i];
        S += a[i];
        maxa = max(maxa, a[i]);
    }
    int MAXS = (int)S;
    int LIMIT = MAXS + maxa + 5; // giới hạn x chúng ta quan tâm

    vector<char> dp_full(MAXS+1, 0);
    dp_full[0] = 1;
    for (int i = 1; i <= N; ++i){
        // iterate backwards to avoid overwrite
        for (int s = MAXS - a[i]; s >= 0; --s){
            if (dp_full[s]) dp_full[s + a[i]] = 1;
        }
    }
    if ((S % 2) != 0 || !dp_full[S/2]) {
        cout << 0 << '\n';
        return 0;
    }

    vector< vector<int> > pref_lists(N+1), suf_lists(N+2);
    {
        vector<char> cur(MAXS+1, 0);
        cur[0] = 1;
        pref_lists[0].push_back(0);
        for (int i = 1; i <= N; ++i){
            vector<int> new_sums;
            // for each existing sum s, s+a[i] becomes reachable
            for (int s : pref_lists[i-1]){
                int ns = s + a[i];
                if (!cur[ns]) { // not yet set
                    cur[ns] = 1;
                    new_sums.push_back(ns);
                }
            }
            // merge lists: previous sums remain, plus new ones
            pref_lists[i] = pref_lists[i-1];
            if (!new_sums.empty()){
                pref_lists[i].insert(pref_lists[i].end(), new_sums.begin(), new_sums.end());
            }
        }
    }

    {
        vector<char> cur(MAXS+1, 0);
        cur[0] = 1;
        suf_lists[N+1].push_back(0);
        for (int i = N; i >= 1; --i){
            vector<int> new_sums;
            for (int s : suf_lists[i+1]){
                int ns = s + a[i];
                if (!cur[ns]) {
                    cur[ns] = 1;
                    new_sums.push_back(ns);
                }
            }
            suf_lists[i] = suf_lists[i+1];
            if (!new_sums.empty()){
                suf_lists[i].insert(suf_lists[i].end(), new_sums.begin(), new_sums.end());
            }
        }
    }

    for (int i = 0; i <= N+1; ++i){
        sort(pref_lists[i].begin(), pref_lists[i].end());
        pref_lists[i].erase(unique(pref_lists[i].begin(), pref_lists[i].end()), pref_lists[i].end());
        if (i <= N+1) {
            if (i <= N+1 && !suf_lists[i].empty()) {
                sort(suf_lists[i].begin(), suf_lists[i].end());
                suf_lists[i].erase(unique(suf_lists[i].begin(), suf_lists[i].end()), suf_lists[i].end());
            }
        }
    }

    unordered_map<int,int> cnt;
    cnt.reserve(100000);

    vector<char> Si(MAXS+1, 0);
    for (int i = 1; i <= N; ++i){
        fill(Si.begin(), Si.end(), 0);
        const vector<int> &L = pref_lists[i-1];
        const vector<int> &R = suf_lists[i+1];
        for (int p : L){
            for (int q : R){
                int s = p + q;
                if (!Si[s]){
                    Si[s] = 1;
                    // produce x candidates from s
                    long long x1 = 2LL * s - S + a[i];
                    if (x1 > 0 && x1 <= LIMIT) cnt[(int)x1]++;
                    long long x2 = S - a[i] - 2LL * s;
                    if (x2 > 0 && x2 <= LIMIT) cnt[(int)x2]++;
                }
            }
        }
    }
    vector <int> ans;
    for (auto &pr : cnt){
        if (pr.second == N) ans.push_back(pr.first);
    }
    sort(ans.begin(), ans.end());
    cout << ans.size() << '\n';
    if (!ans.empty()){
        for (size_t i = 0; i < ans.size(); ++i){
            if (i) cout << ' ';
            cout << ans[i];
        }
        cout << '\n';
    }
    return 0;
}

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