fork download
copy 
  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. int state[128][SIXTEEN];
  54.  
  55. void input()
  56. {
  57.     scanf("%d %d", &n, &k);
  58.     for(int i=1;i<=n;i++)
  59.     {
  60.         scanf("%d", &a[i]);
  61.     }
  62. }
  63.  
  64. void solve()
  65. {
  66.     memset(state,0,sizeof(state));
  67.     int i,j;
  68.     for(i=1;i<=n;i++)
  69.     {
  70.         state[i][0]=1;
  71.         for(j=1;j<=k;j++)
  72.         {
  73.             state[i][j]=(state[i][j-a[i]]+state[i-1][j])%MOD;
  74.         }
  75.     }
  76.     printf("%d\n", state[n][k]);
  77. }
  78.  
  79. int main()
  80. {
  81.     int i,t;
  82.     scanf("%d", &t);
  83.     for(i=1;i<=t;i++)
  84.     {
  85.         input();
  86.         printf("Case %d: ", i);
  87.         solve();
  88.     }
  89.     return 0;
  90. }
  91.  
Success #stdin #stdout 0s 11336KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/KhRqJo
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!