🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📚 Mới ra mắt – Gói giải đề có lời giải chi tiết · chấm bài tự động · thầy hỗ trợ 1 – 1. Nếu còn phân vân về khóa học chính thức, các em và phụ huynh có thể tham khảo các gói giải đề dưới đây để trải nghiệm trước hệ thống làm bài, cách thầy phân tích – giải bài và sự hỗ trợ trực tiếp của thầy:

• 👉 Gói giải đề Tuyển sinh 10 chuyên Tin Hà Nội 2024 – 2026 – KHTN, ĐHSP · 5 đề · 21 bài · C++ và Python
• 👉 Gói giải đề Tuyển sinh 10 chuyên Tin Phổ thông Năng khiếu TP.HCM 2004 – 2026 – 22 đề · 84 bài · C++ và Python
• 👉 Gói giải đề HSG Tin học lớp 9 TP.HCM 2008 – 2026 – cấp Thành phố · 17 đề · 48 bài · C++ và Python
• 👉 Gói giải đề HSG Tin học lớp 9 Hà Nội 2005 – 2026 – cấp Thành phố · 17 đề · 69 bài · C++ và Python

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Cuối học kỳ, thầy Sơn thuê một chiếc ghe chở học trò đi du khảo trên kênh Xà No. Con kênh được chia thành ~N~ khúc liên tiếp, đánh số từ ~1~ đến ~N~ theo chiều ghe chạy. Khúc thứ ~i~ có độ vui ~a_i~: khúc có vườn cây trái, chợ quê thì ~a_i > 0~; khúc nắng gắt, nước đục, nhiều lục bình thì ~a_i~ có thể âm (học trò thấy mệt và chán).

Thầy Sơn chọn một đoạn khúc liên tiếp ~l, l + 1, \dots, r~ ~(1 \le l \le r \le N)~ để ghe chạy qua. Để học trò đỡ mệt, thầy được phép cho cả lớp ngủ trưa ở một số khúc trong đoạn đã chọn: khi ngủ ở khúc ~i~, cả lớp không thấy gì nên khúc đó được tính độ vui bằng ~0~ (thay cho ~a_i~). Tuy nhiên:

• cả chuyến đi chỉ được ngủ ở tối đa ~K~ khúc;
• không được ngủ ở hai khúc liên tiếp (ngủ dậy thì phải thức ngắm cảnh ít nhất một khúc rồi mới được ngủ tiếp).

Tổng độ vui của chuyến đi là tổng ~a_i~ của các khúc mà cả lớp thức trong đoạn đã chọn. Hãy giúp thầy Sơn chọn đoạn kênh và các khúc ngủ sao cho tổng độ vui là lớn nhất.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên ~N~ và ~K~ ~(1 \le N \le 2 \times 10^5;~ ~0 \le K \le 10)~.
• Dòng thứ hai chứa ~N~ số nguyên ~a_1, a_2, \dots, a_N~ ~(|a_i| \le 10^9)~.

Kết quả

Một số nguyên duy nhất là tổng độ vui lớn nhất có thể đạt được. Lưu ý đoạn kênh được chọn phải có ít nhất một khúc.

Giới hạn (Subtask)

• Subtask 1 (~20\%~ số điểm): ~N \le 15~.
• Subtask 2 (~30\%~ số điểm): ~N \le 3000~ và ~K \ge 1~.
• Subtask 3 (~50\%~ số điểm): không có ràng buộc gì thêm.

💡 Lưu ý khi nộp bằng Python: các em nên chọn ngôn ngữ PyPy 3 thay vì Python 3 để chương trình chạy nhanh hơn nhiều. Giới hạn thời gian cho Python/PyPy ở bài này là 3 giây.

Sample Input 1

9 2
9 7 -3 7 -8 -2 8 5 -1

Sample Output 1

34

Giải thích

Thầy chọn đoạn từ khúc ~1~ đến khúc ~8~ và cho cả lớp ngủ ở khúc ~3~ và khúc ~5~: tổng độ vui là ~9 + 7 + 0 + 7 + 0 + (-2) + 8 + 5 = 34~.

Sample Input 2

4 0
-5 -2 -7 -3

Sample Output 2

-2

Giải thích

Không được ngủ khúc nào (~K = 0~) mà khúc nào cũng có độ vui âm, nên thầy chọn đoạn chỉ gồm một khúc ~2~ có độ vui ~-2~.

Nguồn: Đề tự luyện HSG Tin học lớp 9 (đề tự soạn).