Advertisement
Guest User

Untitled

a guest
May 30th, 2015
362
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.72 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. using namespace std;
  5. typedef long long ll;
  6.  
  7. const ll MOD = (ll)(1e9 + 7);
  8. const int N = 500500;
  9. int n;
  10. ll dp[N];
  11. ll sumdp[N];
  12. ll h[N];
  13. ll m;
  14.  
  15. ll sum(ll x, ll y)
  16. {
  17.     x += y;
  18.     if (x >= MOD) return x - MOD;
  19.     return x;
  20. }
  21. ll sub(ll x, ll y)
  22. {
  23.     x -= y;
  24.     if (x < 0) return x + MOD;
  25.     return x;
  26. }
  27.  
  28. int main()
  29. {
  30.     scanf("%d%lld", &n, &m);
  31.     for (int i = 1; i <= n; i++)
  32.     {
  33.         scanf("%lld", &h[i]);
  34.         h[i] += h[i - 1];
  35.     }
  36.     dp[0] = 1;
  37.     sumdp[1] = 1;
  38.     int idx = 0;
  39.     for (int i = 1; i <= n; i++)
  40.     {
  41.         while(h[i] - h[idx] > m) idx++;
  42.         dp[i] = sub(sumdp[i], sumdp[idx]);
  43.         sumdp[i + 1] = sum(sumdp[i], dp[i]);
  44.     }
  45.     printf("%lld\n", dp[n]);
  46.  
  47.     return 0;
  48. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement