CSES - Houses and Schools | Nhà và Trường

Xem PDF



Tác giả:
Dạng bài
Ngôn ngữ cho phép
Assembly, Awk, C, C#, C++, Clang, Clang++, Cobol, D, Groovy, Haskell, Java, JS, Kotlin, Lua, Node JS, ObjectiveC, OCaml, Output, Pascal, Perl, PHP, Prolog, Pypy, Pypy 3, Python, Ruby, Rust, Scala, Swift
Điểm: 1900 Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

\(n\) ngôi nhà nằm trên một con đường, được đánh số \(1, 2, \ldots, n\). Khoảng cách từ ngôi nhà \(a\) đến \(b\)\(|a - b|\). Bạn biết được số đứa trẻ trong từng căn nhà.

Nhiệm vụ của bạn là thành lập \(k\) ngôi trường sao cho mỗi ngôi trường nằm ở một căn nhà nào đó. Sau đó, những đứa trẻ sẽ đi học ở trường gần chúng nhất. Tổng quãng đường đi bộ nhỏ nhất của những đứa trẻ là gì nếu bạn thực hiện một cách tối ưu?

Input

Dòng đầu vào đầu tiên có hai số nguyên \(n\)\(k\): số ngôi nhà và số ngôi trường. Các ngôi nhà được đánh số \(1, 2, \ldots, n\).

Sau đó, có \(n\) số nguyên \(c_1, c_2, \ldots, c_n\) : số đứa trẻ trong mỗi nhà.

Output

In ra tổng quãng đường nhỏ nhất.

Constraints

  • \(1 \leq k \leq n \leq 3000\)
  • \(1 \leq c_i \leq 10^9\)

Example

Sample Input

6 2
2 7 1 4 6 4

Sample Output

11

Giải thích: Ngôi nhà 2 và 5 sẽ có trường học.


Bình luận

Không có bình luận nào.