제출 #1332989

#제출 시각아이디문제언어결과실행 시간메모리
1332989aaaaaaaaBootfall (IZhO17_bootfall)C++20
28 / 100
1095 ms4164 KiB
#include <bits/stdc++.h>
using namespace std;
const int mxN = 75635;

int a[275], freq[mxN];

bitset<mxN> pref[275], suff[275];

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, sum = 0;
    cin >> n;

    pref[0][0] = suff[n + 1][0] = 1;

    for(int i = 1; i <= n; ++i){
        cin >> a[i];
        sum += a[i];
    }

    for(int i = 1; i <= n; ++i){
        pref[i] = pref[i - 1], suff[n - i + 1] = suff[n - i + 2];
        pref[i] |= pref[i - 1] << a[i];
        suff[n - i + 1] |= suff[n - i + 2] << a[n - i + 1];
    }

    if(sum & 1 || !pref[n][sum / 2]){
        cout << "0\n";
    }else{
        for(int i = 1; i <= n; ++i){
            bitset<mxN> res = suff[i + 1];
            for(int j = 0; j < mxN; ++j){
                if(pref[i - 1][j]){
                    res |= suff[i + 1] << j;
                }
            }
            int rem = sum - a[i];
            for(int j = 0; j < mxN; ++j){
                if(res[j] && j * 2 <= rem && (rem -  j * 2) <= mxN){
                    freq[rem -  j * 2] += 1;
                }
            }
        }
        vector<int> ans;
        for(int i = 0; i < mxN; ++i){
            if(freq[i] == n){
                ans.push_back(i);
            }
        }
        cout << (int) ans.size() << "\n";
        for(auto it : ans){
            cout << it << " ";
        }
    }
    return 0;
}
#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...