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 sub(ll a, ll b)
  27. {
  28.     return ((a % MOD) - (b % MOD) + MOD) % MOD;
  29. }
  30.  
  31. int mul(ll a, ll b)
  32. {
  33.     return ((a % MOD) * (b % MOD)) % MOD;
  34. }
  35.  
  36. int dp[100 + 50][100000 + 50];
  37.  
  38. void solve()
  39. {
  40.  
  41.     int n, sum;
  42.     cin >> n >> sum;
  43.  
  44.     int v[MAX];
  45.     for (int i = 0; i < n; i++)
  46.     {
  47.         cin >> v[i];
  48.     }
  49.  
  50.     dp[n][0] = 1;
  51.  
  52.     for (int idx = n - 1; idx >= 0; idx--)
  53.     {
  54.  
  55.         int prefix[sum + 2] = {};
  56.  
  57.         for (int s = 0; s <= sum; s++)
  58.         {
  59.             prefix[s] = dp[idx + 1][s];
  60.             if (s != 0)
  61.             {
  62.                 prefix[s] = add(prefix[s], prefix[s - 1]);
  63.             }
  64.         }
  65.  
  66.         for (int s = 0; s <= sum; s++)
  67.         {
  68.  
  69.             int from = s - v[idx];
  70.             int to = s;
  71.  
  72.             dp[idx][s] = prefix[to];
  73.             if (from >= 1)
  74.             {
  75.                 dp[idx][s] = sub(dp[idx][s], prefix[from - 1]);
  76.             }
  77.         }
  78.     }
  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 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/rIjsa4
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!