Lễ hội
View as PDF
Ở ngôi làng nọ, có ~n~ ngôi nhà nằm trên một đường thẳng. Biết trưởng làng sống ở nhà thứ ~1~, nhà thứ ~i~ nằm cách nhà trưởng làng đúng ~a_i~ km về phía đông.
Sắp tới mùa Tết, trưởng làng muốn chọn ra một số địa điểm trên đường thẳng để chuẩn bị tổ chức hội hoa xuân. Chi phí để chuẩn bị một hội hoa xuân là ~k~ coin.
Sau khi chuẩn bị xong, tất cả người dân sẽ di chuyển đến hội hoa xuân gần nhà mình nhất để tham gia. Nếu một người dân ở cách địa điểm ~x~ km, chi phí để di chuyển sẽ là ~x~ coin.
Hãy tìm cách chọn một số địa điểm sao cho tổng chi phí tổ chức lễ hội và di chuyển là nhỏ nhất.
Nói cách khác, nếu như ta chọn ~m~ địa điểm, địa điểm thứ ~i~ nằm cách nhà trưởng làng đúng ~s_i~ km về phía đông, tổng chi phí tổ chức lễ hội và di chuyển sẽ là ~k \cdot m + \sum \limits_{i = 1}^{n} \min \limits_{j = 1}^{m} |a_i - s_j|~.
Input
Dòng đầu tiên chứa hai số nguyên dương ~n~ (~1 \le n \le 2 \cdot 10^5~) — số ngôi nhà trong làng và ~k~ (~1 \le k \le 10^9~) — chi phí tổ chức một hội hoa xuân.
Dòng tiếp theo chứa ~n~ số nguyên dương ~a_1, a_2, \ldots, a_n~ (~0 = a_1 < a_2 < \ldots < a_n \le 10^9~), trong đó ~a_i~ thể hiện khoảng cách từ nhà thứ ~1~ đến nhà thứ ~i~.
Output
Một dòng duy nhất chứa đáp án của bài toán: tổng chi phí tổ chức lễ hội và di chuyển nhỏ nhất.
Sample Input 1
4 5
0 1 6 10
Sample Output 1
15
Notes
Ở test mẫu, ta có thể tổ chức lễ hội tại các địa điểm ~1~ và ~9~.
Khi đó, người dân ở nhà ~1~ và ~2~ sẽ di chuyển tới địa điểm thứ nhất, người dân ở nhà ~3~ và ~4~ sẽ di chuyển tới địa điểm thứ hai.
Tổng chi phí tổ chức lễ hội và di chuyển sẽ là ~2 \cdot 5 + |0 - 1| + |1 - 1| + |6 - 9| + |10 - 9| = 15~.
Comments
This comment is hidden due to too much negative feedback. Show it anyway.