LOJ-1231 :: Coin Change (I)

#include<bits/stdc++.h>
using namespace std ;

int coin[55] , no[55] ,n ,k;
long long int dp[55][1005] ;
int mod=100000007  ;

long long int call (int i , int amount)
{
    int j ;
      if (i==n)
    {
        if (amount==0) return 1 ;
        else return 0 ;
    }
     long long int &res =dp[i][amount] ;

      if (res != -1) return res ;
      res=0 ;
    for (j=0 ; j<=no[i] ; j++)
    {
        if (amount-(coin[i]*j)>=0)
            res+= call(i+1,amount-(coin[i]*j))%mod ;
        else  break ;
    }
    res=res%mod ;
   return res ;
}


int main ()
{
    int t ,j ,it ;
    cin>>t ;
    for (it=1 ; it<=t ; it++)
    {
        cin>>n>>k ;
        memset(dp,-1,sizeof (dp)) ;
        for(j=0 ; j<n ; j++) cin>>coin[j] ;
        for (j=0 ; j<n ;j++) cin>>no[j] ;

        printf ("Case %d: %lld\n",it,call(0,k) ) ;

    }

    return 0 ;
}