Changyoung and the Jump
InterviewTime limit2sMemory limit512 MB
Given gaps between N red blocks and a stride K, find the longest run of blocks he can step through using at most one jump over a too-large gap.
- Level
Medium5 of 10
- Topics
- Two pointers, Sliding window, Array, Greedy
- Solved
- No attempts yet
Problem
Changyoung has gotten off the bus and is walking to work. The path he walks is mostly paved with gray sidewalk blocks, though now and then there are red sidewalk blocks. He recalls that as a child he used to step only on the red blocks. He decides to walk while stepping on as many red blocks as possible without touching a gray block in between.
From here on, for convenience, we call every red sidewalk block a block.
There are N blocks lying in a straight line in front of Changyoung. Number the blocks 1, 2, ... N in order of increasing distance from him. Block i and block i+1 are a distance Li apart. Changyoung can move a length K in one step, and to move from any block i to block i+1 he must satisfy Li ≤ K. However, he can jump at most once to move from block i to block i+1 regardless of the distance. If Changyoung cannot step on the next block, his record ends there. He never turns back to step on a block he has already stepped on.
Changyoung wants to choose the best starting point and set the highest record for consecutive red-block stepping. Find the maximum number of blocks he can step on consecutively.
Input
The first line gives the number of red sidewalk blocks N and Changyoung's stride K.
The second line gives the distances Li between consecutive red sidewalk blocks, N-1 of them.
Output
Print the maximum number of red sidewalk blocks Changyoung can step on consecutively when the starting point may be chosen freely and he can jump at most once.
Constraints
- 2 ≤ N ≤ 100,000
- 1 ≤ K, Li ≤ 100