fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define mod 100000007
  6. #define siz 50
  7.  
  8.  
  9. int dp[52][1005];
  10. int coin[siz],cointNum[siz];
  11. int k,n;
  12.  
  13. int call(int i,int amount)
  14. {
  15.     if(i>=n)
  16.     {
  17.         if(amount==0)
  18.             return 1;
  19.         else
  20.             return 0;
  21.     }
  22.  
  23.     if(dp[i][amount != -1])
  24.         return dp[i][amount];
  25.  
  26.     int ret1=0,ret2=0;
  27.  
  28.     for(int p=1;p<cointNum[i];p++)
  29.     {
  30.         if(amount - coin[i] >= 0)
  31.             ret1=call(i,amount-coin[i]);
  32.     }
  33.  
  34.     ret2=call(i+1,amount);
  35.  
  36.     return dp[i][amount] = (ret1+ret2)%mod;
  37. }
  38.  
  39.  
  40.  
  41. int main()
  42. {
  43.     int tc,cn,loop,num,res;
  44.  
  45.     memset(dp,-1,sizeof(dp));
  46.     scanf("%d",&tc);
  47.     for(cn=1;cn<=tc;cn++)
  48.     {
  49.         scanf("%d %d",&n,&k);
  50.         //loop=2*n;
  51.         for(int i=0;i<n;i++)
  52.         {
  53.             scanf("%d",&coin[i]);
  54.  
  55.         }
  56.  
  57.         for(int j=0;j<n;j++)
  58.         {
  59.             scanf("%d",&cointNum[j]);
  60.  
  61.         }
  62.  
  63.         res=call(0,k);
  64.         printf("Case %d: %d\n",cn,res);
  65.     }
  66.  
  67.     return 0;
  68. }
  69.  
Success #stdin #stdout 0s 3500KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/zSGnYq
language:
C++14 (gcc 8.3)
created:
9 years 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!