SHARE
TWEET

Untitled

a guest Apr 19th, 2016 156 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //BISMILLAHIR RAHMANIR RAHIM
  2. #include<iostream>
  3. #include<cstdio>
  4. #include<cstring>
  5. #include<map>
  6. #include<string>
  7. #include<set>
  8. #include<cmath>
  9. #include<cctype>
  10. #include<stack>
  11. #include<cstdlib>
  12. #include<utility>
  13. #include<vector>
  14. #include<deque>
  15. #include<queue>
  16. #include<algorithm>
  17.  
  18. #define sc scanf
  19. #define si(t) scanf("%d",&t)
  20. #define sl(t) scanf("%I64d",&t)
  21. #define sii(a,b) scanf("%d%d",&a,&b)
  22.  
  23. #define P(a) printf("%d\n",a)
  24. #define PLN(a) printf("%I64d ",a)
  25. #define pf printf
  26.  
  27. #define gcd(a,b) __gcd(a,b)
  28. #define ff first
  29. #define ss second
  30. #define pr1(a) cout<<a<<endl
  31. #define pr2(a,b) cout<<a<<" "<<b<<endl
  32.  
  33. #define pii pair<int,int>
  34. #define pi acos(-1.0)
  35. #define PI 3.1415926535897932385
  36. #define Sin(a) sin((pi*a)/180)
  37. #define siz 1000001
  38. #define mem(ar) memset(ar,-1,sizeof ar)
  39. #define one(x) __builtin_popcount(x)
  40. typedef long long ll;
  41. using namespace std;
  42. //int dx[]= {-1,-1,0,0,1,1};
  43. //int dy[]= {-1,0,-1,1,0,1};
  44. //int dx[]= {0,0,1,-1};/*4 side move*/
  45. //int dy[]= {-1,1,0,0};/*4 side move*/
  46. //int dx[]= {1,1,0,-1,-1,-1,0,1};/*8 side move*/
  47. //int dy[]= {0,1,1,1,0,-1,-1,-1};/*8 side move*/
  48. //int dx[]={1,1,2,2,-1,-1,-2,-2};/*night move*/
  49. //int dy[]={2,-2,1,-1,2,-2,1,-1};/*night move*/
  50. map<ll,bool>visi;
  51. int make;
  52. int dp[50][1000][20];
  53. int coin[1000];
  54. int use[1001];
  55. int n,m;
  56. int call(int i,int take_i,int amount)
  57. {
  58.     if(i>=n)
  59.     {
  60.         if(amount==0)return 1;
  61.         else return 0;
  62.     }
  63.     if(dp[i][amount][take_i]!=-1) return (dp[i][amount][take_i]);
  64.     int ret1=0,ret2=0;
  65.     if(take_i<use[i])
  66.     {
  67.         if(amount-coin[i]>=0) ret1=(call(i,take_i+1,amount-coin[i]))%100000007;
  68.     }
  69.     ret2=(call(i+1,0,amount))%100000007;
  70.     return dp[i][amount][take_i]=(ret1+ret2)%100000007;
  71. }
  72. int main()
  73. {
  74.     int t,cs=1;
  75.     scanf("%d",&t);
  76.     while(t--)
  77.     {
  78.         mem(dp);
  79.         int i;
  80.         scanf("%d%d",&n,&m);
  81.         for(i=0; i<n; i++)
  82.             scanf("%d",&coin[i]);
  83.         for(i=0; i<n; i++)
  84.             scanf("%d",&use[i]);
  85.         printf("Case %d: %d\n",cs++,call(0,0,m)%100000007);
  86.     }
  87.     return 0;
  88. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top