Advertisement
Josif_tepe

Untitled

Nov 3rd, 2023
552
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.27 KB | None | 0 0
  1. #include <iostream>
  2. #include <queue>
  3. #include <vector>
  4. #include <fstream>
  5. #include <cstring>
  6. using namespace std;
  7. const int maxn = 505;
  8. int dp[2][maxn][maxn];
  9. int main() {
  10.     ios_base::sync_with_stdio(false);
  11.     int n, k;
  12.     cin >> n >> k;
  13.    
  14.     memset(dp, 0, sizeof dp);
  15.     vector<int> v(n);
  16.    
  17.     for(int i = 0; i < n; i++) {
  18.         cin >> v[i];
  19.     }
  20.     dp[0][0][0] = 1;
  21.     for(int at = 0; at < n; at++) {
  22.         int next_at = 1 - (at % 2);
  23.         int current_at = at % 2;
  24.         for(int sum = 0; sum <= k; sum++) {
  25.             for(int k_sum = 0; k_sum <= sum; k_sum++) {
  26.                 dp[next_at][sum][k_sum] = dp[current_at][sum][k_sum];
  27.                 if(sum >= v[at]) {
  28.                     dp[next_at][sum][k_sum] |= dp[current_at][sum - v[at]][k_sum];
  29.                     if(k_sum >= v[at]) {
  30.                         dp[next_at][sum][k_sum] |= dp[current_at][sum - v[at]][k_sum - v[at]];
  31.                     }
  32.                 }
  33.             }
  34.         }
  35.     }
  36.     vector<int> res;
  37.     for(int i = 0; i <= k; i++) {
  38.         if(dp[(n % 2)][k][i]) {
  39.             res.push_back(i);
  40.         }
  41.     }
  42.     cout << (int) res.size() << endl;
  43.     for(int i = 0; i < res.size(); i++) {
  44.         cout << res[i] << " ";
  45.     }
  46.     return 0;
  47. }
  48.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement