fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long int
  4. #define all(v) v.begin(), v.end()
  5. #define run ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0);
  6. #define ms(a, x) memset(a, x, sizeof(a));
  7.  
  8. int dp[1000009];
  9. int solve(int n, int k, vector<int> &a)
  10. {
  11.     if (k < 0)
  12.         return INT_MAX;
  13.  
  14.     if (k == 0)
  15.         return 0;
  16.  
  17.     if (dp[k] != -1)
  18.         return dp[k];
  19.     int ans = INT_MAX;
  20.  
  21.     for (int i = 0; i < n; i++)
  22.    ans = min(ans, 1 + solve(n, k - a[i], a));
  23.  
  24.  
  25.     return dp[k] = ans;
  26. }
  27.  
  28. signed main()
  29. {
  30.  
  31.     run;
  32.  
  33.     int n, i, k, ans = 0;
  34.     ms(dp, -1);
  35.  
  36.     cin >> n >> k;
  37.  
  38.     vector<int> a(n, 0);
  39.  
  40.     for (i = 0; i < n; i++)
  41.         cin >> a[i];
  42.  
  43.     sort(all(a));
  44.  
  45.     ans = solve(n, k, a);
  46.     if (ans >= INT_MAX)
  47.         ans = -1;
  48.  
  49.     cout << ans;
  50. }
Success #stdin #stdout 0.01s 11444KB
comments (?)
stdin
copy 
3 11
1 5 7
stdout
copy 
3
https://ideone.com/1Dqqgg
language:
C++14 (gcc 8.3)
created:
2 years 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!