fork(1) download
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4.  
  5. const int mod = 1e9 + 7;
  6.  
  7. int ways(vector<int> &arr,vector<vector<int> > &dp, int idx, int sum)
  8. {
  9. if(idx < 0)
  10. return (sum == 0);
  11. if(sum == 0)
  12. return 1;
  13. if(sum < 0)
  14. return 0;
  15.  
  16. int &ans = dp[idx][sum];
  17. if(ans != -1)
  18. return ans;
  19.  
  20. if(sum >= arr[idx])
  21. ans = (ways(arr, dp, idx, sum - arr[idx]) + ways(arr, dp, idx - 1, sum)) % mod;
  22. else
  23. ans = ways(arr, dp, idx - 1, sum);
  24.  
  25. return ans;
  26. }
  27.  
  28. int main()
  29. {
  30.  
  31. ios_base::sync_with_stdio(false);
  32. cin.tie(0);
  33. cout.tie(0);
  34.  
  35. // #ifndef ONLINE_JUDGE
  36. // freopen("input.txt", "r", stdin);
  37. // freopen("output.txt", "w", stdout);
  38. // #endif
  39.  
  40. int n, val;
  41. cin >> n >> val;
  42.  
  43. vector<int> arr(n);
  44.  
  45. for(int i = 0; i < n; i++)
  46. cin >> arr[i];
  47.  
  48. vector<vector<int> > dp(n, vector<int>(val + 1, -1));
  49.  
  50. cout << ways(arr, dp, n - 1, val);
  51.  
  52. return 0;
  53. }
Success #stdin #stdout 0s 4560KB
stdin
3 2000
1 1500 1000
stdout
4