fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4. const int MOD = 1000000007;
  5. const int MX = 1000001;
  6.  
  7. ll modExp(ll base, ll power) {
  8.     if (power == 0) return 1;
  9.     ll cur = modExp(base, power / 2);
  10.     cur = (cur * cur) % MOD;
  11.     if (power % 2) cur = (cur * base) % MOD;
  12.     return cur;
  13. }
  14. ll inv(ll x) { return modExp(x, MOD - 2); }
  15. ll mul(ll A, ll B) { return (A * B) % MOD; }
  16. ll add(ll A, ll B) { return (A + B) % MOD; }
  17. ll sub(ll A, ll B) { return (A - B + MOD) % MOD; }
  18.  
  19. bool dp[501][501][501];
  20.  
  21.  
  22.  
  23.  
  24. int main() {
  25.     ios::sync_with_stdio(false);
  26.     cin.tie(nullptr);
  27.     int n, k;
  28.     cin >> n >> k;
  29.     vector<int> arr(n);
  30.     dp[0][0][0] = true;
  31.     // dp[i][j][k]  = true if there exists some subset sum of j that also includes w    
  32.     for (int i = 0; i < n; i++) cin >> arr[i];
  33.     for (int i = 0; i < n; i++) {
  34.  
  35.         for (int a  = 0 ; a <=  k ; a  ++) {
  36.             for (int b  = 0 ; b <=  k ; b  ++) {
  37.                  if (dp[i][a][b]) {
  38.                     int val = arr[i]; 
  39.                     dp[i + 1][a][b] = true; 
  40.                     if (a + val <= k) {
  41.                         dp[i][a + val][b] = true; 
  42.                         if (b + val <= k) {
  43.                             dp[i][a + val][b + val] = true;
  44.                         }
  45.                     }
  46.                 }
  47.             }
  48.     }
  49. }
  50.     vector<int> res;
  51.     for (int i = 0  ; i <= k ; i ++) {
  52.         if (dp[n][k][i]) {
  53.             res.push_back(i);
  54.         } 
  55.     }    
  56.     cout << res.size() << endl;
  57.     for (int i = 0 ; i < res.size() ; i ++) {
  58.         cout << res[i] << ' '; 
  59.     }
  60.      return 0;
  61. }
  62.  
Success #stdin #stdout 0.01s 5676KB
comments (?)
stdin
copy 
6 18
5 6 1 10 12 2
stdout
copy 
19
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
https://ideone.com/4r5Dwn
language:
C++ (gcc 8.3)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!