Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdio>
- #include <cstdlib>
- using namespace std;
- typedef long long ll;
- const ll MOD = (ll)(1e9 + 7);
- const int N = 500500;
- int n;
- ll dp[N];
- ll sumdp[N];
- ll h[N];
- ll m;
- ll sum(ll x, ll y)
- {
- x += y;
- if (x >= MOD) return x - MOD;
- return x;
- }
- ll sub(ll x, ll y)
- {
- x -= y;
- if (x < 0) return x + MOD;
- return x;
- }
- int main()
- {
- scanf("%d%lld", &n, &m);
- for (int i = 1; i <= n; i++)
- {
- scanf("%lld", &h[i]);
- h[i] += h[i - 1];
- }
- dp[0] = 1;
- sumdp[1] = 1;
- int idx = 0;
- for (int i = 1; i <= n; i++)
- {
- while(h[i] - h[idx] > m) idx++;
- dp[i] = sub(sumdp[i], sumdp[idx]);
- sumdp[i + 1] = sum(sumdp[i], dp[i]);
- }
- printf("%lld\n", dp[n]);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement