Advertisement
Josif_tepe

Untitled

Feb 16th, 2022
848
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.06 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. int n;
  4. int k;
  5. int niza[105];
  6. int dp[100005];
  7. using namespace std;
  8. int main()
  9. {
  10.     cin>>n;
  11.     cin>>k;
  12.     int mod = 1e9 + 7;
  13.     for(int i=0; i<n; i++){
  14.         cin>>niza[i];
  15.     }
  16.         for(int j=0; j<=k; j++){
  17.             dp[j] = 0;
  18.         }
  19.    
  20.     dp[0] = 1;
  21.     // dp[j] --> broj na nacini da stigneme so j candies
  22.     for(int i = 0; i < n; i++) {
  23.         vector<int> pref_sum(k + 10, 0);
  24.         for(int j = k; j >= 0; j--) {
  25.             int x = j + 1, y = j + min(niza[i], k - j);
  26.             if(x <= y) {
  27.                 pref_sum[x] += dp[j];
  28.                 pref_sum[x] %= mod;
  29.                 pref_sum[y + 1] -= dp[j];
  30.                 if(pref_sum[y + 1] < 0) {
  31.                     pref_sum[y + 1] += mod;
  32.                 }
  33.                
  34.             }
  35.         }
  36.         int sum = 0;
  37.         for(int j = 0; j <= k; j++) {
  38.             sum += pref_sum[j];
  39.             sum %= mod;
  40.             dp[j] += sum;
  41.             dp[j] %= mod;
  42.         }
  43.     }
  44.     cout << dp[k] << endl;
  45.     return 0;
  46. }
  47.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement