HSG 9 Nghệ An 2026 - Dàn đèn
ĐỀ BÀI: DÀN ĐÈN
Sau khi hoàn thành bài thi, Alice, Bob cùng các bạn thi lập trình tham quan trải nghiệm tại công viên ánh sáng. Công viên có một dàn đèn gồm \(n\) bóng đèn được đặt vị trí theo phương nằm ngang. Các đèn đánh số thứ tự từ \(1\) đến \(n\) theo hướng từ trái sang phải. Mỗi bóng đèn có ánh sáng màu xanh hoặc màu đỏ.
Nhìn vào dàn đèn với ánh sáng màu xanh, màu đỏ rực rỡ, Alice đã yêu cầu Bob trả lời câu hỏi:
Nếu phải chọn \(k\) bóng đèn kế nhau và đổi trạng thái màu của các bóng đèn đó (màu xanh chuyển sang màu đỏ, màu đỏ chuyển sang màu xanh) thì số lượng bóng đèn màu xanh trên dàn đèn nhiều nhất là bao nhiêu?
Yêu cầu: Hãy đưa ra câu trả lời đúng của Bob.
Dữ liệu vào:
- Dòng thứ nhất ghi hai số nguyên dương \(n, k\) (\(3 \le n \le 10^6; 1 \le k \le n\)).
- Dòng thứ hai ghi \(n\) số nguyên \(a_1, a_2, \dots, a_n\), \(0 \le a_i \le 1\), trong đó \(a_i = 0\) biểu thị đèn \(i\) có ánh sáng màu đỏ, \(a_i = 1\) biểu thị đèn \(i\) có ánh sáng màu xanh.
Kết quả ra:
- In ra một số nguyên duy nhất là số lượng bóng đèn màu xanh nhiều nhất có thể đạt được khi chọn \(k\) bóng đèn kế nhau và đổi màu sáng của \(k\) bóng đèn được chọn.
Điểm số:
- \(40\%\) số điểm ứng với \(k = 1\);
- \(40\%\) số điểm ứng với \(k = 2\);
- \(20\%\) số điểm còn lại không có giới hạn gì thêm.
Ví dụ:
Input
8 2
1 1 0 0 0 1 1 0
Output
6
Giải thích: Có 8 bóng đèn, hiện tại bóng đèn thứ 3 và thứ 4 đang màu đỏ. Nếu chọn 2 đèn này và chuyển sang màu xanh, thì trạng thái màu sắc của 8 đèn là: \(1, 1, 1, 1, 0, 1, 1, 0\). Số lượng bóng đèn sáng màu xanh là 6. Đây là số lượng đèn màu xanh lớn nhất có thể đạt được khi chọn 2 bóng đèn kế nhau và đổi màu của chúng.
Input
8 2
1 1 1 1 1 1 1 1
Output
6
Giải thích: Hiện tại tất cả 8 bóng đèn đều có màu xanh. Nếu chọn 2 đèn kế nhau và chuyển thành màu đỏ thì số đèn màu xanh còn lại là 6.
Input
8 1
1 0 1 0 1 0 1 1
Output
6
Giải thích: Hiện tại có 5 đèn màu xanh và 3 đèn màu đỏ. Nếu chọn đèn thứ 2 và chuyển sang màu xanh thì có 6 đèn màu xanh.