fork(1) download
copy 
  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
comments (?)
stdin
copy 
3 2000
1 1500 1000
stdout
copy 
4
https://ideone.com/7zKt7d
language:
C++14 (gcc 8.3)
created:
4 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!