Planting flowers - MarisaOJ: Marisa Online Judge

Planting flowers

Time limit: 1000 ms
Memory limit: 256 MB
Marisa has $n$ flower pots arranged consecutively. Planting flowers in the $i$-th pot costs $a_i$. Marisa has a budget of $t$, so she cannot plant flowers in all pots. The "ugliness" of the flower pots is defined as the length of the longest contiguous segment of pots without flowers. Help Marisa find a way to plant flowers such that the ugliness is minimized while staying within the budget. ### Input - The first line contains two positive integers $n$ and $t$. - The second line contains $n$ integers $a_i$. ### Output - Output a single integer representing the minimum possible ugliness. ### Constraints - $1 \le n \le 5 \times 10^4$. - $0 \le a_i \le 3000$. - $1 \le t \le 10^8$. ### Example Input: ``` 17 11 6 4 5 2 5 3 4 5 2 3 4 5 2 3 6 3 5 ``` Output: ``` 3 ``` Explanation:
a 6 4 5 2 5 3 4 5 2 3 4 5 2 3 6 3 5
Plant? √ √ √ √