Bài 3. Lựa chọn (HSG THPT Hà Tĩnh - Khối 11 2026)
Xem dạng PDFTrong quá trình phân tích dữ liệu lớn, các hệ thống máy tính thường ghi nhận một chuỗi giá trị số theo thứ tự thời gian. Giả sử hệ thống ghi nhận ~n~ giá trị liên tiếp ~a_1, a_2, \ldots, a_n~. Do nhiều nguyên nhân khác nhau như sai số thiết bị, nhiễu môi trường hoặc lỗi làm tròn, các giá trị thu được có thể chưa phản ánh chính xác xu hướng thực tế. Để khắc phục vấn đề này, hệ thống cho phép hiệu chỉnh mỗi giá trị ban đầu bằng cách tăng hoặc giảm không quá ~k~ đơn vị. Sau khi hiệu chỉnh, mỗi giá trị ~a_i~ được thay thế bằng một số nguyên ~b_i (1 \le i \le n)~ thỏa mãn ~a_i - k \le b_i \le a_i + k~. Một tiêu chí quan trọng để đánh giá chất lượng của dãy số sau hiệu chỉnh là mức độ tăng dần theo thời gian. Cụ thể, người ta quan tâm đến độ dài lớn nhất của một dãy con không giảm dài nhất trong dãy sau khi hiệu chỉnh. Dãy con không giảm dài nhất không nhất thiết gồm các phần tử liên tiếp, nhưng phải giữ nguyên thứ tự xuất hiện ban đầu.
Yêu cầu: Hãy lựa chọn các giá trị ~b_1, b_2, \ldots, b_n~ (mỗi ~b_i~ nằm trong khoảng cho phép) sao cho độ dài của dãy con không giảm dài nhất của dãy ~b~ là lớn nhất. In ra độ dài lớn nhất đó.
Dữ liệu vào
Gồm hai dòng:
- Dòng đầu tiên chứa hai số nguyên ~n~ và ~k~.
- Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \ldots, a_n~.
Kết quả
Một số nguyên là độ dài lớn nhất của dãy con không giảm dài nhất có thể đạt được.
Ví dụ
Input 1
5 0
1 2 2 1 4
Output 1
4
Input 2
5 2
3 1 4 2 5
Output 2
5
Ví dụ 1: với ~k = 0~, dãy ~b~ giữ nguyên như dãy ~a~, dãy con không giảm dài nhất là 1, 2, 2, 4 có độ dài 4. Ví dụ 2: có thể chọn ~b = (1, 2, 3, 4, 5)~ phù hợp với các khoảng cho phép, khi đó cả dãy là không giảm, độ dài 5.
Ràng buộc
- Subtask 1 (30% số điểm): ~k = 0, 1 \le n \le 10^3, |a_i| \le 10^9~.
- Subtask 2 (20% số điểm): ~k = 1, 1 \le n \le 10^3, |a_i| \le 10^9~.
- Subtask 3 (20% số điểm): ~0 \le k \le 500, 1 \le n \le 10^3, |a_i| \le 10^9~.
- Subtask 4 (30% số điểm): ~0 \le k \le 10^9, 1 \le n \le 10^3, |a_i| \le 10^9~.
Chương trình đọc dữ liệu từ bàn phím (stdin) và ghi kết quả ra màn hình (stdout).