mickypinata

USACO-T033: Money Systems

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