Độ khó: Khó (4/4 điểm)

🎓 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

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

Thầy Sơn có ~N~ học sinh đứng thành một hàng, học sinh thứ ~i~ (tính từ đầu hàng) có điểm năng lực ~a_i~. Thầy muốn chia cả hàng thành một số nhóm, mỗi nhóm gồm các học sinh đứng liên tiếp trong hàng, mỗi học sinh thuộc đúng một nhóm (không được đổi chỗ học sinh).

Mỗi nhóm cần một phòng học riêng nên tốn chi phí cố định ~C~. Ngoài ra, nhóm càng chênh lệch thì càng khó dạy: một nhóm có điểm lớn nhất là ~\max~ và điểm nhỏ nhất là ~\min~ tốn thêm chi phí ~\max - \min~. Như vậy chi phí của một nhóm là ~C + (\max - \min)~, và chi phí của cách chia là tổng chi phí các nhóm.

Hãy giúp thầy Sơn tìm cách chia có tổng chi phí nhỏ nhất.

Dữ liệu vào

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

Kết quả

Một số nguyên duy nhất là tổng chi phí nhỏ nhất.

Giới hạn (Subtask)

• Subtask 1 (~30\%~ số điểm): ~N \le 5000~.
• Subtask 2 (~20\%~ số điểm): ~a_1 \le a_2 \le \dots \le a_N~.
• 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à 5 giây.

Sample Input 1

5 3
1 5 1 2 8

Sample Output 1

10

Sample Input 2

9 5
1 3 2 20 21 20 5 4 6

Sample Output 2

20

Giải thích

• Ví dụ 1: chia thành ~[1, 5, 1, 2]~ và ~[8]~, chi phí ~(3 + 4) + (3 + 0) = 10~. Nếu để mỗi bạn một nhóm thì tốn ~5 \times 3 = 15~.
• Ví dụ 2: chia thành ~[1, 3, 2]~, ~[20, 21, 20]~, ~[5, 4, 6]~, chi phí ~(5 + 2) + (5 + 1) + (5 + 2) = 20~.

Nguồn: Đề tự luyện HSG Tin học quốc gia (đề tự soạn).