Advertisement
mickypinata

USACO-T044: Stamps

Dec 22nd, 2021
979
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2. ID: mickyta1
  3. TASK: stamps
  4. LANG: C++
  5. */
  6.  
  7. #include <bits/stdc++.h>
  8. using namespace std;
  9.  
  10. const int K = 200 + 5;
  11. const int X = 2e6 + 5;
  12.  
  13. int arr[K], dp[X];
  14.  
  15. int main(){
  16.     freopen("stamps.in", "r", stdin);
  17.     freopen("stamps.out", "w", stdout);
  18.  
  19.     int n, limCnt;
  20.     scanf("%d%d", &limCnt, &n);
  21.     for(int i = 1; i <= n; ++i){
  22.         scanf("%d", &arr[i]);
  23.     }
  24.     for(int x = 1; x <= 2e6; ++x){
  25.         int mn = 1e9;
  26.         for(int i = 1; i <= n; ++i){
  27.             if(x >= arr[i]){
  28.                 mn = min(mn, 1 + dp[x - arr[i]]);
  29.             }
  30.         }
  31.         dp[x] = mn;
  32.         if(dp[x] > limCnt){
  33.             cout << x - 1 << '\n';
  34.             break;
  35.         }
  36.     }
  37.  
  38.     fclose(stdin);
  39.     fclose(stdout);
  40.     return 0;
  41. }
  42.  
Advertisement
RAW Paste Data Copied
Advertisement