Problem B
Beach
Maja has had enough of all the big seaside estates that occupy the coastline. Instead, she wants to create a long and beautiful beach that anyone can use. She is planning to buy a segment of plots along the coast to create the beach.
Maja has a budget of $B$ kronor, and the plots along the coast cost $A_0,A_1,\dots ,A_{N-1}$ kronor, from left to right. Maja can buy one segment of adjacent plots. What is the longest segment of plots that she can afford to buy?
Input
The first line contains the two integers $N$ and $B$, the number of plots and Maja’s budget.
The second line contains $N$ integers $A_0,A_1,\dots ,A_{N-1}$, the costs of the plots.
Output
Print one integer, the maximum number of adjacent plots Maja can afford to buy.
Constraints and Scoring
-
$1 \leq N \leq 10^5$.
-
$0 \leq B \leq 10^9$.
-
$1 \leq A_ i \leq 1000$ for each $i$ such that $0 \leq i \leq N-1$.
Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.
|
Group |
Score |
Limits |
|
$1$ |
$21$ |
$A_0 = A_1 = \dots = A_{N-1}$ |
|
$2$ |
$30$ |
$N \leq 500 $ |
|
$3$ |
$49$ |
No additional constraints |
Example
In the first example, Maja has enough money to buy all the plots.
In the second example, Maja can buy either the first three, or the last three plots.
In the third example, Maja can buy the plots with indices $2,3,4,5,6$ and $7$. This will cost $3+4+6+2+1+2 = 18$ kronor, which Maja can afford. However, it is not possible to buy more than $6$ plots.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 14 4 7 3 |
3 |
| Sample Input 2 | Sample Output 2 |
|---|---|
4 36 11 5 7 14 |
3 |
| Sample Input 3 | Sample Output 3 |
|---|---|
9 18 1 5 3 4 6 2 1 2 4 |
6 |
