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.  
  35. void solve()
  36. {
  37.  
  38.     cin >> n >> sum;
  39.  
  40.     for (int i = 0; i < n; i++)
  41.     {
  42.         cin >> v[i];
  43.     }
  44.  
  45.     int dp[n + 1][sum + 1] = {};
  46.     dp[n][0] = 1;
  47.  
  48.     for (int idx = n - 1; idx >= 0; idx--)
  49.     {
  50.         for (int s = 0; s <= sum; s++)
  51.         {
  52.             for (int i = 0; i <= v[idx]; i++)
  53.             {
  54.                 if (sum - i >= 0)
  55.                 {
  56.                     dp[idx][s] = add(dp[idx][s], dp[idx + 1][s - i]);
  57.                 }
  58.             }
  59.         }
  60.     }
  61.  
  62.     cout << dp[0][sum];
  63. }
  64.  
  65. signed main()
  66. {
  67.     ya_sayed_ya_badawy int t = 1;
  68.     // cin >> t;
  69.  
  70.     while (t--)
  71.     {
  72.         solve();
  73.         // cout << endl;
  74.     }
  75.     return 0;
  76. }
Success #stdin #stdout 0s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/3JZA78
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!