Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <queue>
- #include <vector>
- #include <fstream>
- #include <cstring>
- using namespace std;
- const int maxn = 505;
- int dp[2][maxn][maxn];
- int main() {
- ios_base::sync_with_stdio(false);
- int n, k;
- cin >> n >> k;
- memset(dp, 0, sizeof dp);
- vector<int> v(n);
- for(int i = 0; i < n; i++) {
- cin >> v[i];
- }
- dp[0][0][0] = 1;
- for(int at = 0; at < n; at++) {
- int next_at = 1 - (at % 2);
- int current_at = at % 2;
- for(int sum = 0; sum <= k; sum++) {
- for(int k_sum = 0; k_sum <= sum; k_sum++) {
- dp[next_at][sum][k_sum] = dp[current_at][sum][k_sum];
- if(sum >= v[at]) {
- dp[next_at][sum][k_sum] |= dp[current_at][sum - v[at]][k_sum];
- if(k_sum >= v[at]) {
- dp[next_at][sum][k_sum] |= dp[current_at][sum - v[at]][k_sum - v[at]];
- }
- }
- }
- }
- }
- vector<int> res;
- for(int i = 0; i <= k; i++) {
- if(dp[(n % 2)][k][i]) {
- res.push_back(i);
- }
- }
- cout << (int) res.size() << endl;
- for(int i = 0; i < res.size(); i++) {
- cout << res[i] << " ";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement