fork download
  1. /*********************/
  2. //Hard work beats talent when talent doesn’t work hard
  3. /*********************/
  4. #include <iostream>
  5. using namespace std;
  6. #include<bits/stdc++.h>
  7. /*#define int long long*/
  8. #define wh while (t--)
  9. #define pb push_back
  10. #define popcount __builtin_popcountll
  11. #define beg begin()
  12. #define endi end()
  13. #define f first
  14. #define sec second
  15. #define endl '\n'
  16. #define iso ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  17. int mod = 1e9+7;
  18. int arr[(int)1e3+4] ;
  19. int n ;
  20. int x ;
  21. int memo[(int)1e6+5][100+2] ;
  22. int solve(int sum ,int index )
  23. {
  24.  
  25. if(sum==0)
  26. {
  27. return 1 ;
  28. }
  29. if(sum<0)
  30. {
  31. return 0 ;
  32. }
  33. if(index>=n)
  34. {
  35. return 0 ;
  36.  
  37. }
  38. if(memo[sum][index]!=-1)
  39. return memo[sum][index]%mod ;
  40. int take =solve(sum-arr[index],index)%mod ;
  41. int no_take =solve(sum,index+1)%mod ;
  42. int ans =(take+no_take)%mod;
  43. return memo[sum][index]=ans%mod ;
  44.  
  45.  
  46. }
  47. int32_t main() {
  48. iso ;
  49. memset(memo ,-1 ,sizeof(memo)) ;
  50. cin>> n >>x ;
  51. for(int i=0 ;i<n ;i++)
  52. {
  53. cin>> arr[i] ;
  54. }
  55. cout<<solve(x,0) ;
  56.  
  57.  
  58. }
Success #stdin #stdout 0.05s 402080KB
stdin
Standard input is empty
stdout
1