Advertisement
sherry_ahmos

Untitled

Dec 1st, 2022
1,195
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.46 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <map>
  4. //#include <bits/stdc++.h>
  5. #include <algorithm>
  6. #include <cmath>
  7. using namespace std;
  8.  
  9. #define ll long long
  10. #define cy cout << "YES"
  11. #define cn cout << "NO"
  12. #define nl "\n"
  13. #define fi first
  14. #define se second
  15. #define all(v) v.begin(), v.end()
  16. #define sz(s) s.size()
  17. template <typename T = int>
  18. istream &operator>>(istream &in, vector<T> &v)
  19. {
  20.     for (auto &x : v)
  21.         in >> x;
  22.     return in;
  23. }
  24.  
  25. template <typename T = int>
  26. ostream &operator<<(ostream &out, const vector<T> &v)
  27. {
  28.     for (const T &x : v)
  29.         out << x << " ";
  30.     return out;
  31. }
  32.  
  33. void sherry()
  34. {
  35.     ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  36. #ifndef ONLINE_JUDGE
  37.     freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
  38. #endif
  39. }
  40. ll n, x;
  41. vector<ll> v, dp;
  42. ll coins(ll curr)
  43. {
  44.     if (curr == 0)
  45.         return 0;
  46.     ll &ret = dp[curr];
  47.     if (~ret)
  48.         return ret;
  49.     ret = 1e9;
  50.     for (ll i = 0; i < n; i++)
  51.     {
  52.         if (curr - v[i] >= 0)
  53.         {
  54.             ret = min(ret, 1 + coins(curr - v[i]));
  55.         }
  56.     }
  57.     return ret;
  58. }
  59. void solve()
  60. {
  61.     cin >> n >> x;
  62.     v.resize(n);
  63.     cin >> v;
  64.     dp.assign(1e6, -1);
  65.     int ans = coins(x);
  66.     if (ans == 1e9)
  67.         cout << "-1";
  68.     else
  69.         cout << ans;
  70. }
  71. int main()
  72. {
  73.     sherry();
  74.     int t = 1;
  75.     // cin >> t;
  76.     while (t--)
  77.         solve();
  78.     return 0;
  79. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement