P3594 [POI 2015 R3] Wolf Pits (Trous de loup)

Given a sequence of length $n$, you have one chance to choose a contiguous segment of length at most $d$ and change all numbers inside it to $0$. Find the longest contiguous segment such that the sum of all numbers within this segment does not exceed $p$.

The first line contains three integers, $n, p, d$. The second line contains $n$ integers; the $i$-th integer is $w_i$, the $i$-th number in the sequence.

Output a single integer, the length of the longest valid segment after the modification.

Constraints For $100\%$ of the testdata, $1 \le d \le n \le 2 \times 10^6$, $0 \le p \le 10^{16}$, $1 \leq w_i \leq 10^9$. ---- Original title: Wilcze doły. Translated by ChatGPT 5