Advertisement
Josif_tepe

Untitled

Nov 3rd, 2023
437
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.17 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.  
  9. int main() {
  10.     ios_base::sync_with_stdio(false);
  11.     int n, k;
  12.     cin >> n >> k;
  13.     int dp[n + 1][k + 1][k + 1];
  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.         for(int sum = 0; sum <= k; sum++) {
  23.             for(int k_sum = 0; k_sum <= sum; k_sum++) {
  24.                 dp[at + 1][sum][k_sum] = dp[at][sum][k_sum];
  25.                 if(sum >= v[at]) {
  26.                     dp[at + 1][sum][k_sum] |= dp[at][sum - v[at]][k_sum];
  27.                     if(k_sum >= v[at]) {
  28.                         dp[at + 1][sum][k_sum] |= dp[at][sum - v[at]][k_sum - v[at]];
  29.                     }
  30.                 }
  31.             }
  32.         }
  33.     }
  34.     vector<int> res;
  35.     for(int i = 0; i <= k; i++) {
  36.         if(dp[n][k][i]) {
  37.             res.push_back(i);
  38.         }
  39.     }
  40.     cout << (int) res.size() << endl;
  41.     for(int i = 0; i < res.size(); i++) {
  42.         cout << res[i] << " ";
  43.     }
  44.     return 0;
  45. }
  46.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement