Submission #377084

#	Time	Username	Problem	Language	Result	Execution time	Memory
377084		ijxjdjd	Bootfall (IZhO17_bootfall)	C++14	100 / 100	128 ms	33896 KiB

bootfall

#include <bits/stdc++.h>
#define FR(i, N) for (int i = 0; i < int(N); i++)
#define all(x) begin(x), end(x)

using namespace std;

using ll = long long;

const int MAXN = 500;
const int MAXA = 500;
stack<bitset<2*MAXN*MAXA>> st;
bitset<2*MAXN*MAXA> nt[MAXN];
bitset<2*MAXN*MAXA> tot;
bitset<2*MAXN*MAXA> pos;
vector<int> arr;
int S = 0;
void recur(int tl, int tr) {
    if (tl == tr) {
        nt[tl] = (st.top()>>(S-arr[tr]));
        if (tr == arr.size()-1) {
            tot = st.top()|(st.top() << (2*arr[tr]));
            tot >>= S;
        }
    }
    else {
        int tm = (tl + tr)/2;
        st.push(st.top());
        for (int i = tl; i <= tm; i++) {
            st.top() |= (st.top() << (2*arr[i]));
        }
        recur(tm+1, tr);
        st.pop();
        st.push(st.top());
        for (int i = tm+1; i <= tr; i++) {
            st.top() |= (st.top() << (2*arr[i]));
        }
        recur(tl, tm);
        st.pop();
    }

}
int main() {
	cin.tie(0);
	cin.sync_with_stdio(0);
	int N;
	cin >> N;
	st.emplace();
	st.top()[0] = 1;
	pos.set();
	FR(i, N) {
        int a;
        cin >> a;
        S += a;
        arr.push_back(a);
    }
    recur(0, N-1);
    if (!tot[0]) {
        cout << "0" << '\n';
        return 0;
    }
    else {
        FR(i, N) {
            pos &= (nt[i]);
        }
        vector<int> res;
        for (int i = 1; i < 2*MAXN*MAXA; i++) {
            if (pos[i]) {
                res.push_back(i);
            }
        }
        cout << res.size() << '\n';
        for (int r : res) {
            cout << r << " ";
        }
    }
	return 0;
}

Compilation message (stderr)

bootfall.cpp: In function 'void recur(int, int)':
bootfall.cpp:20:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |         if (tr == arr.size()-1) {
      |             ~~~^~~~~~~~~~~~~~~

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