Submission #1333123

#TimeUsernameProblemLanguageResultExecution timeMemory
1333123aaaaaaaaBootfall (IZhO17_bootfall)C++20
28 / 100
1092 ms4112 KiB
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("O3")
#pragma GCC target("sse4,avx2,fma,avx")
using namespace std;

const int mxN = 72905;

int a[272], freq[mxN];
bitset<mxN> pref[272], suff[272];

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 = pref[i-1]._Find_first(); j < mxN; j = pref[i-1]._Find_next(j)) res |= suff[i + 1] << j;
            int rem = sum - a[i];
            for(int j = res._Find_first(); j < mxN; j = res._Find_next(j)) {
                if(j * 2 > rem) break;
                if((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...