fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. #define all(x) x.begin(), x.end()
  4. #define rall(x) x.rbegin(), x.rend()
  5. #define sz(x) (int)(x).size()
  6.  
  7. using namespace std;
  8. const double pi = acos(-1);
  9. const int mod = 1e9 + 7;
  10. const int N = 1e2 + 5, M = 1e2 + 2, K = 1e5 + 5;
  11.  
  12. int dx[] = {0, 0, 1, -1, 1, 1, -1, -1};
  13. int dy[] = {1, -1, 0, 0, 1, -1, 1, -1};
  14.  
  15. void fast()
  16. {
  17. #ifndef ONLINE_JUDGE
  18.     freopen("input.txt", "r", stdin);
  19.     freopen("output.txt", "w", stdout);
  20. #endif
  21.     ios::sync_with_stdio(false);
  22.     cin.tie(nullptr), cout.tie(nullptr);
  23. }
  24.  
  25. int n, k;
  26. int arr[N], dp[N][K];
  27.  
  28. int sol(int i, int rem)
  29. {
  30.     if (i == n)
  31.         return (rem > 0 || rem < 0 ? 0 : 1);
  32.  
  33.     if (rem == 0)
  34.         return 1;
  35.     if (rem < 0)
  36.         return 0;
  37.  
  38.     int &ret = dp[i][rem];
  39.  
  40.     if (~ret)
  41.         return ret;
  42.  
  43.     ret = 0;
  44.     for (int j = 0; j <= arr[i]; j++)
  45.         ret += sol(i + 1, rem - j);
  46.     return ret;
  47. }
  48.  
  49. int32_t main()
  50. {
  51.     fast();
  52.  
  53.     cin >> n >> k;
  54.  
  55.     for (int i = 1; i <= n; i++)
  56.         cin >> arr[i];
  57.  
  58.     if (n == 1)
  59.     {
  60.         cout << (arr[1] >= k);
  61.         return 0;
  62.     }
  63.  
  64.     memset(dp, 0, sizeof dp);
  65.  
  66.     dp[1][0] = 1;
  67.     for (int i = 0; i <= arr[1]; i++)
  68.         dp[1][i] = 1;
  69.  
  70.     for (int i = 1; i <= k; i++)
  71.         dp[1][i] += dp[1][i - 1];
  72.  
  73.     for (int i = 2; i <= n; i++)
  74.     {
  75.         for (int j = 0; j <= k; j++)
  76.         {
  77.             if (j <= arr[i])
  78.                 (dp[i][j] += dp[i - 1][j]) %= mod;
  79.             else
  80.                 (dp[i][j] += dp[i - 1][j] - dp[i - 1][j - arr[i] - 1]) %= mod;
  81.         }
  82.  
  83.         if (i != n)
  84.             for (int j = 1; j <= k; j++)
  85.             {
  86.                 dp[i][j] += dp[i][j - 1];
  87.                 dp[i][j] %= mod;
  88.             }
  89.     }
  90.  
  91.     cout << dp[n][k] % mod;
  92.  
  93.     return 0;
  94. }
Success #stdin #stdout 0.02s 85708KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ftdv4r
language:
C++ (gcc 8.3)
created:
4 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!