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

Dọc một con sông có ~N~ làng, đánh số từ ~1~ đến ~N~ theo chiều nước chảy. Làng thứ ~i~ ở vị trí ~x_i~ (tính theo km từ đầu nguồn, ~x_1 < x_2 < \dots < x_N~) và sau vụ mùa có ~g_i~ tấn lúa.

Thầy Sơn cần xây không quá ~K~ kho lúa, mỗi kho đặt tại một làng, trong đó bắt buộc có một kho ở làng ~N~ (cửa sông). Thuyền chở lúa chỉ đi xuôi dòng, nên lúa của mỗi làng được chở tới kho gần nhất ở phía hạ lưu (kho tại chính làng đó hoặc kho đầu tiên nằm sau làng đó). Chở một tấn lúa đi ~1~ km tốn chi phí ~1~, nên lúa của làng ~i~ chở tới kho ở làng ~j~ ~(j \ge i)~ tốn ~g_i \times (x_j - x_i)~.

Hãy chọn vị trí các kho để tổng chi phí chở lúa của cả ~N~ làng là nhỏ nhất.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên ~N~ và ~K~ ~(1 \le K \le N \le 2 \times 10^5)~.
• Dòng thứ hai chứa ~N~ số nguyên ~x_1, x_2, \dots, x_N~ ~(0 \le x_1 < x_2 < \dots < x_N \le 10^9)~.
• Dòng thứ ba chứa ~N~ số nguyên ~g_1, g_2, \dots, g_N~ ~(1 \le g_i \le 1000)~.

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 (~20\%~ số điểm): ~N \le 300~.
• Subtask 2 (~30\%~ số điểm): ~K \le 20~.
• 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 2
0 2 3 7 10
3 1 2 2 5

Sample Output 1

16

Sample Input 2

6 3
1 4 5 9 12 20
2 2 1 5 1 3

Sample Output 2

18

Giải thích

• Ví dụ 1: đặt kho ở làng ~3~ (vị trí ~3~) và làng ~5~. Làng ~1, 2, 3~ chở về kho ở vị trí ~3~ tốn ~3 \times 3 + 1 \times 1 + 0 = 10~; làng ~4~ chở về làng ~5~ tốn ~2 \times 3 = 6~. Tổng ~16~.
• Ví dụ 2: đặt kho ở các làng ~2, 4, 6~ (vị trí ~4, 9, 20~): chi phí ~2 \times 3 + 1 \times 4 + 1 \times 8 = 18~.

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