fork download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/inIGo6
language:
C++ (gcc 8.3)
created:
3 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!