Advertisement
newb_ie

LIGHT OJ 1231

Jul 20th, 2020
637
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  /*
  2.        _________
  3.       /         \
  4.      /  _     _  \
  5.     /   0     0   \
  6.    |       ||     |
  7.    |              | => HI
  8.     \     -----   /
  9.      \           /
  10.       \_ _ _ _ _/
  11.  */
  12.  
  13. #include<bits/stdc++.h>
  14. using namespace std;
  15. using lli = int64_t;
  16. const int maxN = 1010;
  17. lli grid[51][maxN];
  18. lli solve(int coins[],int coins_count[],int idx,int k,int n){
  19.     if(idx == n or k == 0){
  20.         return (k == 0);
  21.     }
  22.     if(grid[idx][k] != -1){
  23.         return grid[idx][k];
  24.     }
  25.     lli res = 0;
  26.     for(int i = 0;i <= coins_count[idx]; i++){
  27.         if(k - (coins[idx] * i) >= 0){
  28.             res += solve(coins,coins_count,idx + 1,k - (coins[idx] * i),n);
  29.         }
  30.     }
  31.     return grid[idx][k] = res % 100000007;
  32. }
  33. int main(){
  34.     ios::sync_with_stdio(false);
  35.     cin.tie(nullptr);
  36.     int T;
  37.     cin >> T;
  38.     for(int t = 1; t <= T; t++){
  39.         memset(grid,-1,sizeof(grid));
  40.         int n,k;
  41.         cin >> n >> k;
  42.         int coins[51],coins_count[51];
  43.         for(int i = 0;i < n; i++){
  44.             cin >> coins[i];
  45.         }
  46.         for(int i = 0;i < n; i++){
  47.             cin >> coins_count[i];
  48.         }
  49.         cout << "Case " << t << ": " << solve(coins,coins_count,0,k,n) << "\n";
  50.     }
  51. }
Advertisement
RAW Paste Data Copied
Advertisement