Bài 2. Dịch vụ (HSG THPT Hà Tĩnh - Khối 11 2026)
Xem dạng PDFTrong quá trình quy hoạch hạ tầng đô thị, chính quyền địa phương cần xây dựng một số trạm phục vụ cộng đồng (ví dụ: trạm ~y~ tế, trạm cứu trợ, trạm dịch vụ công) nhằm đáp ứng nhu cầu của người dân một cách hiệu quả và công bằng. Người dân sinh sống tập trung thành từng khu dân cư dọc theo một tuyến đường chính, có thể coi như một trục tọa độ. Toàn khu vực có ~n~ khu dân cư, được đánh số từ 1 đến ~n~. Khu dân cư thứ ~i~ nằm tại vị trí có tọa độ nguyên ~x_i~ trên trục đường và có ~s_i~ người dân sinh sống. Chính quyền dự kiến xây dựng ~k~ trạm phục vụ cộng đồng.
Mỗi trạm phải được đặt tại vị trí của một khu dân cư để thuận tiện cho việc quản lý và vận hành. Khi cần sử dụng dịch vụ, mỗi người dân sẽ đến trạm phục vụ cộng đồng gần khu dân cư nơi mình sinh sống nhất. Mức độ bất tiện của một người dân được tính bằng khoảng cách từ khu dân cư của họ đến trạm phục vụ cộng đồng gần nhất. Mức độ bất tiện của toàn bộ khu vực được xác định bằng tổng mức độ bất tiện của tất cả người dân.
Yêu cầu: Cho thông tin về vị trí các khu dân cư và số dân của mỗi khu, hãy xác định tổng mức độ bất tiện nhỏ nhất khi xây dựng ~k~ trạm phục vụ cộng đồng một cách hợp lý nhất.
Dữ liệu vào
Gồm ba dòng:
- Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~k (1 \le k \le 10, k \le n \le 10^3)~.
- Dòng thứ hai chứa ~n~ số nguyên ~x_1, x_2, \ldots, x_n (0 \le x_i \le 10^9)~ là tọa độ của khu dân cư thứ ~i~.
- Dòng thứ ba chứa ~n~ số nguyên dương ~s_1, s_2, \ldots, s_n (1 \le s_i \le 10^5)~ là số dân của khu dân cư thứ ~i~.
Kết quả
Một số nguyên duy nhất là tổng mức độ bất tiện nhỏ nhất của toàn bộ khu vực.
Ví dụ
Input 1
4 1
1 2 3 5
1 2 2 3
Output 1
10
Input 2
4 2
1 2 3 5
1 2 2 3
Output 2
3
Ví dụ 1: trạm đặt tại khu dân cư số 3, tổng mức độ bất tiện là ~1 \times 2 + 2 \times 1 + 3 \times 0 + 3 \times 2 = 10~. Ví dụ 2: hai trạm đặt tại khu số 2 và số 4; người dân khu 1, 2, 3 đến trạm ở khu 2, người dân khu 4 đến trạm ở khu 4, tổng bằng 3.
Ràng buộc
- Subtask 1 (50% số điểm): ~1 \le n \le 20, k = 1~.
- Subtask 2 (25% số điểm): ~1 \le n \le 20, k \le 10~.
- Subtask 3 (25% số điểm): ~n \le 10^3, k = 1~.
Chương trình đọc dữ liệu từ bàn phím (stdin) và ghi kết quả ra màn hình (stdout).