p415.cpp
======================
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream &operator<<(ostream &out, const pair<T1, T2> &x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream &operator>>(istream &in, pair<T1, T2> &x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream &operator>>(istream &in, vector<T> &a) {
    for(auto &x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream &operator<<(ostream &out, const vector<T> &a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int n, x;
vector<int> a;

void read() {
    cin >> n >> x;
    a.resize(n);
    cin >> a;
}

const int MAXLEN = (int)1e4 + 42;

template<int bit_len = 1>
void solve(int _x) {
    if(_x > bit_len) {
        solve<std::min(bit_len * 2, MAXLEN)>(_x);
        return;
    }

    vector<bitset<bit_len>> dp_prev(n + 2);
    vector<bitset<bit_len>> dp_suff(n + 2);
    
    dp_prev[0][0] = 1;
    dp_suff[n + 1][0] = 1;
    for(int i = 1; i <= n; i++) {
        dp_prev[i] = dp_prev[i - 1] | (dp_prev[i - 1] << a[i - 1]);
    }

    for(int i = n; i >= 1; i--) {
        dp_suff[i] = dp_suff[i + 1] | (dp_suff[i + 1] << a[i - 1]);
    }

    vector<int> ans;
    for(int i = 1; i <= n; i++) {
        bool ok = false;
        for(int j = 0; j <= x; j++) {
            if(dp_prev[i - 1][j] && dp_suff[i + 1][_x - j]) {
                ok = true;
                break;
            }
        }

        if(!ok) {
            ans.push_back(a[i - 1]);
        }
    }

    cout << ans.size() << '\n';
    cout << ans << '\n';
}

void solve() { solve(x); }

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}

=================
statement.txt
======================
415. Necessary Coins
Time limit per test: 1.25 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard



Vasya has been on vacation on Mars. He's a big fan of foreign coins, and thus has collected exactly one martian coin of each denomination, for a total of n coins: a1 martian dollars, a2 martian dollars, etc, an martian dollars. Unfortunately, he couldn't stand ordering the Pan Galactic Gargle Blaster at the Starport, and has to pay for it — it costs x martian dollars. Vasya is wondering which of his coins are absolutely necessary to do so (i.e., he is forced to abandon them). They don't offer change at the Starport Mars.

Input
The input file contains two integer numbers n and x (1 ≤ n ≤ 200, 1 ≤ x ≤ 104), followed by n distinct integer numbers ai (1 ≤ ai ≤ x).

Output
On the first line of output, print the amount of denominations of coins that appear in any subset that sums to x martian dollars. On the second line of output, print the denominations themselves, in any order, separated with single spaces. It is guaranteed that there exists at least one way to pay x martian dollars with the given coins.

Example(s)
sample input
sample output
5 18
1 2 3 5 10
2
5 10


=================
