fork download 
  1. /*
  2. ID: untamed
  3. PROG: COINCHANGE2
  4. LANG: C++
  5. */
  6.  
  7. #include<cstdio>
  8. #include<iostream>
  9. #include<algorithm>
  10. #include<string>
  11. #include<cstring>
  12. #include<vector>
  13. #include<stack>
  14. #include<queue>
  15. #include<deque>
  16. #include<map>
  17. #include<set>
  18. #include<limits>
  19. #include<climits>
  20. #include<cmath>
  21. #include<functional>
  22. #include<ctime>
  23. #include<cstdlib>
  24. #include<fstream>
  25. #include<typeinfo>
  26.  
  27. const int ONE = 1<<10;
  28. const int TWO = 1<<11;
  29. const int FOUR = 1<<12;
  30. const int EIGHT = 1<<13;
  31. const int SIXTEEN = 1<<14;
  32. const int THIRTY = 1<<15;
  33. const int SIXTY = 1<<16;
  34. const int ONE_HUNDRED = 1<<17;
  35. const int TWO_HUNDRED = 1<<18;
  36. const int FIVE_HUNDRED = 1<<19;
  37. const int MILLION = 1<<20;
  38.  
  39. using namespace std;
  40.  
  41. typedef long long int ll;
  42. typedef short int i16;
  43. typedef unsigned long long int u64;
  44. typedef unsigned int u32;
  45. typedef unsigned short int u16;
  46. typedef unsigned char u8;
  47.  
  48. const int MOD = 100000007;
  49.  
  50. int n,k;
  51. int a[128];
  52.  
  53. void input()
  54. {
  55.     scanf("%d %d", &n, &k);
  56.     for(int i=1;i<=n;i++)
  57.     {
  58.         scanf("%d", &a[i]);
  59.     }
  60. }
  61.  
  62. bool used[128][SIXTEEN];
  63. int state[128][SIXTEEN];
  64.  
  65. int recurse(int current_coin, int k_now)
  66. {
  67.     if(k_now<0)
  68.         return 0;
  69.     if(k_now==0)
  70.         return 1;
  71.     if(current_coin>n)
  72.         return 0;
  73.     if(used[current_coin][k_now])
  74.         return state[current_coin][k_now];
  75.     int ans;
  76.     ans=(recurse(current_coin+1,k_now)+recurse(current_coin,k_now-a[current_coin]))%MOD;
  77.     used[current_coin][k_now]=true;
  78.     state[current_coin][k_now]=ans;
  79.     return ans;
  80. }
  81.  
  82. void solve()
  83. {
  84.     printf("%d\n", recurse(1,k));
  85. }
  86.  
  87. int main()
  88. {
  89.     int i,t;
  90.     scanf("%d", &t);
  91.     for(i=1;i<=t;i++)
  92.     {
  93.         memset(used,0,sizeof(used));
  94.         input();
  95.         printf("Case %d: ", i);
  96.         solve();
  97.     }
  98.     return 0;
  99. }
Success #stdin #stdout 0s 13384KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/HZrx97
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!