Đ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...