fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define ll long long
  6. #define ull unsigned long long
  7. #define initial first
  8. #define added second
  9. #define sort_all(v) sort(v.begin(), v.end())
  10.  
  11. #define ya_sayed_ya_badawy            \
  12.     ios_base::sync_with_stdio(false); \
  13.     cin.tie(NULL);
  14.  
  15. const int MAX = 100 + 50;
  16. const int MAX_N = 1e5 + 50;
  17. int MOD = 1e9 + 7;
  18. const int OO = 1e9;
  19. const double EPS = (double)1e-9;
  20.  
  21. int add(ll a, ll b)
  22. {
  23.     return ((a % MOD) + (b % MOD)) % MOD;
  24. }
  25.  
  26. int mul(ll a, ll b)
  27. {
  28.     return ((a % MOD) * (b % MOD)) % MOD;
  29. }
  30.  
  31. int n, sum;
  32. int v[MAX];
  33.  
  34. int mem[MAX][MAX_N];
  35.  
  36. int dp(int idx, int sum)
  37. {
  38.  
  39.     if(sum < 0)
  40.     {
  41.         return 0;
  42.     }
  43.  
  44.     if (idx == n)
  45.     {
  46.         return (sum == 0);
  47.     }
  48.  
  49.     int &ret = mem[idx][sum];
  50.     if (ret != -1)
  51.     {
  52.         return ret;
  53.     }
  54.  
  55.     ret = 0;
  56.  
  57.     for (int i = 0; i <= v[idx]; i++)
  58.     {
  59.         if (sum - i >= 0)
  60.         {
  61.             ret = add(ret, dp(idx + 1, sum - i));
  62.         }
  63.     }
  64.  
  65.     return ret;
  66. }
  67.  
  68. void solve()
  69. {
  70.  
  71.     cin >> n >> sum;
  72.  
  73.     for (int i = 0; i < n; i++)
  74.     {
  75.         cin >> v[i];
  76.     }
  77.  
  78.     memset(mem, -1, sizeof(mem));
  79.  
  80.     cout << dp(0, sum);
  81. }
  82.  
  83. signed main()
  84. {
  85.     ya_sayed_ya_badawy int t = 1;
  86.     // cin >> t;
  87.  
  88.     while (t--)
  89.     {
  90.         solve();
  91.         // cout << endl;
  92.     }
  93.     return 0;
  94. }
Success #stdin #stdout 0.01s 62080KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/mIQ6ee
language:
C++14 (gcc 8.3)
created:
3 days 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!