vector<vector<bool> >にしててTLEった。こういうのなくせばratingは100以上上がると思うんだけどなくなってくれない。

## solution

DP. $O(nk^2)$.

Let $\mathrm{dp} : k+1 \to \mathcal{P}(k+1)$ be $\mathrm{dp}(x) = \{ y \mid \phi_x(y) \}$, the set of sums of subsets of the subsets whose sum is $x$. Update this function for each coin $c_i$ with $O(k^2)$ simply, then the complexity is $O(nk^2)$ in total.

## implementation

Don’t use vector<set<int> > or vector<vector<int> >. Use vector<vector<bool> > or the similar one.

#include <iostream>
#include <vector>
#include <algorithm>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
#define repeat_reverse(i,n) for (int i = (n)-1; (i) >= 0; --(i))
#define whole(f,x,...) ([&](decltype((x)) y) { return (f)(begin(y), end(y), ## __VA_ARGS__); })(x)
using namespace std;
int main() {
// input
int n, k; cin >> n >> k;
vector<int> cs(n); repeat (i,n) cin >> cs[i];
// calc
vector<vector<bool> > f(k+1, vector<bool>(k+1));
f[0][0] = true;
for (int c : cs) {
repeat_reverse (i,k+1) {
int j = i-c;
if (j < 0) break;
repeat (x,k+1) if (f[j][x]) {
f[i][x    ] = true;
f[i][x + c] = true;
}
}
}
// output
cout << whole(count, f[k], true) << endl;
int j = 0;
repeat (x,k+1) if (f[k][x]) {
if (j ++) cout << ' ';
cout << x;
}
cout << endl;
return 0;
}