SHARE
TWEET

Untitled

a guest Jan 24th, 2020 59 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <stdlib.h>
  3. #include <vector>
  4. #include <unordered_map>
  5. #include <unordered_set>
  6. #include <limits>
  7. #include <cmath>
  8. #include <bits/stdc++.h>
  9. using namespace std;
  10.  
  11. int main() {
  12.     ios_base::sync_with_stdio(false);
  13.     cin.tie(NULL);
  14.  
  15.     int n;
  16.     long long x, c, mn;
  17.     const long long LLMAX = __LONG_LONG_MAX__;
  18.     cin >> n >> x;
  19.  
  20.     long long coins[n];
  21.     for (int i = 0; i < n; i++) {
  22.         cin >> c;
  23.         coins[i] = c;
  24.     }
  25.  
  26.     sort(coins.begin(), coins.end());
  27.  
  28.     vector<long long> dp = {0};
  29.     for (int i = 1; i <=x; i++){
  30.         mn = LLMAX;
  31.         for (auto c: coins) {
  32.             if (i-c >= 0) {
  33.                 if (dp[i-c] != LLMAX) {
  34.                     mn = min(mn, dp[i-c] + 1);
  35.                 }
  36.             }
  37.  
  38.         }
  39.         dp.push_back(mn);
  40.     }
  41.  
  42.     if (dp[x] == LLMAX) {
  43.         cout << -1;
  44.     } else {
  45.         cout << dp[x];
  46.     }
  47.  
  48.     return 0;
  49.  
  50. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top