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

Cuối năm học, thầy Sơn tổ chức giải đấu lập trình đồng đội cho lớp. ~N~ học sinh đã xếp thành một hàng dọc, học sinh thứ ~i~ (tính từ đầu hàng) có điểm năng lực là ~a_i~.

Để các đội được thành lập nhanh chóng, thầy Sơn quy định: không ai được đổi chỗ trong hàng, thầy chỉ "cắt" hàng thành các đoạn liên tiếp, mỗi đoạn là một đội. Mỗi học sinh thuộc đúng một đội, và mỗi đội phải có ít nhất ~L~ và nhiều nhất ~R~ học sinh.

Thầy Sơn muốn các thành viên trong một đội có năng lực sát nhau để làm việc ăn ý. Độ lệch của một đội là hiệu giữa điểm năng lực lớn nhất và nhỏ nhất của các thành viên trong đội đó (đội mà mọi người bằng điểm nhau thì có độ lệch ~0~).

Hãy giúp thầy Sơn chia hàng thành các đội sao cho tổng độ lệch của tất cả các đội là nhỏ nhất.

Dữ liệu vào

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

Kết quả

Một số nguyên duy nhất là tổng độ lệch nhỏ nhất. Nếu không có cách chia nào thỏa mãn, in ra -1.

Giới hạn (Subtask)

• Subtask 1 (~20\%~ số điểm): ~N \le 200~.
• Subtask 2 (~30\%~ số điểm): ~N \le 5000~.
• 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

8 2 4
7 3 1 2 7 9 5 4

Sample Output 1

8

Sample Input 2

9 2 3
2 8 8 8 8 5 2 3 2

Sample Output 2

10

Sample Input 3

5 3 4
1 2 3 4 5

Sample Output 3

-1

Giải thích

• Ví dụ 1: chia thành ~4~ đội ~[7, 3], [1, 2], [7, 9], [5, 4]~ với độ lệch lần lượt ~4, 1, 2, 1~, tổng bằng ~8~.
• Ví dụ 2: một cách chia tối ưu là ~[2, 8, 8], [8, 8, 5], [2, 3, 2]~ với tổng độ lệch ~6 + 3 + 1 = 10~.
• Ví dụ 3: mỗi đội có ~3~ hoặc ~4~ học sinh nên ~5~ học sinh không thể chia thành 1 đội (quá đông) hay từ 2 đội trở lên (thiếu người).

Nguồn: Đề tự luyện HSG Tin học lớp 12 do thầy Nguyễn Việt Nam Sơn biên soạn (đề tự soạn).