Advertisement
Josif_tepe

Untitled

Oct 2nd, 2022
1,044
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.25 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstring>
  3. #include <vector>
  4. using namespace std;
  5. typedef long long ll;
  6. int n, k;
  7. int arr[100005];
  8. // dp[k_left] --> brojot na nacini taka sto imame iskoristeno k_left candies
  9. int dp[100005];
  10. const int MOD = 1e9 + 7;
  11. int main()
  12. {
  13.     ios_base::sync_with_stdio(false);
  14.     cin >> n >> k;
  15.     for(int i = 0; i < n; i++) {
  16.         cin >> arr[i];
  17.     }
  18.     memset(dp, 0, sizeof dp);
  19.     dp[0] = 1;
  20.    
  21.     for(int i = 0; i < n; i++) {
  22.         vector<int> prefix_sum(k + 1, 0);
  23.         for(int candies = k; candies >= 0; candies--) {
  24.             int x = dp[candies];
  25.             int L = candies + 1;
  26.             int R = candies + min(arr[i], k - candies);
  27.             if(L <= R) {
  28.                 prefix_sum[L] += x;
  29.                 prefix_sum[L] %= MOD;
  30.                 if(R + 1 <= k) {
  31.                     prefix_sum[R + 1] -= x;
  32.                     prefix_sum[R + 1] += MOD;
  33.                     prefix_sum[R + 1] %= MOD;
  34.                 }
  35.             }
  36.            
  37.         }
  38.         int pref = 0;
  39.         for(int j = 0; j <= k; j++) {
  40.             pref += prefix_sum[j];
  41.             pref %= MOD;
  42.             dp[j] += pref;
  43.             dp[j] %= MOD;
  44.         }
  45.     }
  46.     cout << dp[k] << endl;
  47.     return 0;
  48. }
  49.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement