Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //BISMILLAHIR RAHMANIR RAHIM
- #include<iostream>
- #include<cstdio>
- #include<cstring>
- #include<map>
- #include<string>
- #include<set>
- #include<cmath>
- #include<cctype>
- #include<stack>
- #include<cstdlib>
- #include<utility>
- #include<vector>
- #include<deque>
- #include<queue>
- #include<algorithm>
- #define sc scanf
- #define si(t) scanf("%d",&t)
- #define sl(t) scanf("%I64d",&t)
- #define sii(a,b) scanf("%d%d",&a,&b)
- #define P(a) printf("%d\n",a)
- #define PLN(a) printf("%I64d ",a)
- #define pf printf
- #define gcd(a,b) __gcd(a,b)
- #define ff first
- #define ss second
- #define pr1(a) cout<<a<<endl
- #define pr2(a,b) cout<<a<<" "<<b<<endl
- #define pii pair<int,int>
- #define pi acos(-1.0)
- #define PI 3.1415926535897932385
- #define Sin(a) sin((pi*a)/180)
- #define siz 1000001
- #define mem(ar) memset(ar,-1,sizeof ar)
- #define one(x) __builtin_popcount(x)
- typedef long long ll;
- using namespace std;
- //int dx[]= {-1,-1,0,0,1,1};
- //int dy[]= {-1,0,-1,1,0,1};
- //int dx[]= {0,0,1,-1};/*4 side move*/
- //int dy[]= {-1,1,0,0};/*4 side move*/
- //int dx[]= {1,1,0,-1,-1,-1,0,1};/*8 side move*/
- //int dy[]= {0,1,1,1,0,-1,-1,-1};/*8 side move*/
- //int dx[]={1,1,2,2,-1,-1,-2,-2};/*night move*/
- //int dy[]={2,-2,1,-1,2,-2,1,-1};/*night move*/
- map<ll,bool>visi;
- int make;
- int dp[50][1000][20];
- int coin[1000];
- int use[1001];
- int n,m;
- int call(int i,int take_i,int amount)
- {
- if(i>=n)
- {
- if(amount==0)return 1;
- else return 0;
- }
- if(dp[i][amount][take_i]!=-1) return (dp[i][amount][take_i]);
- int ret1=0,ret2=0;
- if(take_i<use[i])
- {
- if(amount-coin[i]>=0) ret1=(call(i,take_i+1,amount-coin[i]))%100000007;
- }
- ret2=(call(i+1,0,amount))%100000007;
- return dp[i][amount][take_i]=(ret1+ret2)%100000007;
- }
- int main()
- {
- int t,cs=1;
- scanf("%d",&t);
- while(t--)
- {
- mem(dp);
- int i;
- scanf("%d%d",&n,&m);
- for(i=0; i<n; i++)
- scanf("%d",&coin[i]);
- for(i=0; i<n; i++)
- scanf("%d",&use[i]);
- printf("Case %d: %d\n",cs++,call(0,0,m)%100000007);
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement