david12457899

CSES Coin Combinations 1

May 13th, 2021
679
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include "bits/stdc++.h"
  2.  
  3. const int max = 1000000007;
  4.  
  5.  
  6.  
  7. int main()
  8. {
  9.    
  10.     int n, x;
  11.     std::cin >> n >> x;
  12.  
  13.     std::vector<int> coins(n);
  14.     std::vector<int> dp(x + 1, 0);
  15.    
  16.     for (int i = 0; i < n; i++)
  17.     {
  18.         std::cin >> coins[i];
  19.     }
  20.  
  21.     dp[0] = 1;
  22.  
  23.     for (int i = 1; i <= x; i++)
  24.     {
  25.         for (int j = 0; j < n; j++)
  26.         {
  27.             if (i - coins[j] >= 0)
  28.             {
  29.                 dp[i] = (dp[i] + dp[i - coins[j]]) % 1000000007;
  30.             }
  31.         }
  32.     }
  33.  
  34.     std::cout << dp[x];
  35.  
  36.     return 0;
  37. }
RAW Paste Data