fork download
copy 
  1. // Coin Change 
  2. #include <iostream>
  3. #include <vector>
  4.  
  5. using namespace std;
  6.  
  7. const int MOD = 100000007;
  8.  
  9. int main() {
  10.     ios_base::sync_with_stdio(false);
  11.     cin.tie(NULL);
  12.  
  13.     int T;
  14.     cin >> T;
  15.  
  16.     for (int caseno = 1; caseno <= T; caseno++) {
  17.         int n, K;
  18.         cin >> n >> K;
  19.  
  20.         vector<int> A(n), C(n);
  21.         for (int i = 0; i < n; i++) {
  22.             cin >> A[i];
  23.         }
  24.         for (int i = 0; i < n; i++) {
  25.             cin >> C[i];
  26.         }
  27.  
  28.         vector<long long> dp(K + 1, 0);
  29.         dp[0] = 1;
  30.  
  31.         for (int i = 0; i < n; i++) {
  32.             int a = A[i];
  33.             int c = C[i];
  34.  
  35.             for (int j = K; j >= a; j--) {
  36.                 for (int t = 1; t <= c; t++) {
  37.                     int rem = j - t * a;
  38.                     if (rem < 0) break;
  39.  
  40.                     dp[j] = (dp[j] + dp[rem]) % MOD;
  41.                 }
  42.             }
  43.         }
  44.  
  45.         cout << "Case " << caseno << ": " << dp[K] << "\n";
  46.     }
  47.  
  48.     return 0;
  49. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/RBs2oj
language:
C++ (gcc 8.3)
created:
18 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!