Đoạn Dài Nhất

Xem dạng PDF

Gửi bài giải


Điểm: 0,01 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 1G
Input: stdin
Output: stdout

Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Cho một dãy ~w~ gồm ~n~ số nguyên dương. Bạn được chọn một đoạn liên tiếp có độ dài không quá ~d~ và gán mọi phần tử trong đoạn đó bằng ~0~. Sau đó, hãy tìm độ dài lớn nhất của một đoạn con liên tiếp có tổng không quá ~p~.

Input

Dòng đầu tiên chứa ba số nguyên ~n~, ~p~ và ~d~ (~1 \le d \le n \le 2 \cdot 10^6~, ~0 \le p \le 10^{16}~).

Dòng thứ hai chứa ~n~ số nguyên ~w_1, w_2, \ldots, w_n~ (~1 \le w_i \le 10^9~).

Output

Một số nguyên duy nhất là độ dài lớn nhất của đoạn con tìm được.

Sample Input 1

9 7 2
3 4 1 9 4 1 7 1 3

Sample Output 1

5

Notes

Gán ~w_4 = w_5 = 0~. Đoạn từ vị trí ~2~ đến vị trí ~6~ có tổng ~4 + 1 + 0 + 0 + 1 = 6 \le 7~ và độ dài ~5~.


Đang tải...