Гэрүүд ба Сургуулиуд

2s

512MB

1788

0%

Advanced Techniques

Гудамжинд $1,2,\dots,n$ гэж дугаарлагдсан $n$ гэр байна. $a$ , $b$ гэрүүдийн хоорондох зай $|a-b|$ . Гэр бүрт хэдэн хүүхэд байгааг мэднэ.

$k$ сургууль байгуулна; сургууль бүр ямар нэг гэрт байрлана. Хүүхэд бүр хамгийн ойрын сургуульдаа явна. Оновчтойгоор үйлдэхэд хүүхдүүдийн нийт явах зай хамгийн багадаа хэд вэ?

https://cses.fi/problemset/task/2087

Оролтын формат

Эхний мөрөнд хоёр бүхэл тоо $n$ ба $k$ : гэрүүдийн тоо ба сургуулиудын тоо. Гэрүүд $1,2\dots,n$ гэж дугаарлагдана.

Дараа нь $n$ бүхэл тоо $c_1,c_2,\dots,c_n$ : гэр бүр дэх хүүхдүүдийн тоо.

Гаралтын формат

Хамгийн бага нийт зайг хэвлэ.

Хязгаарлалт

$1 \le k \le n \le 3000$
$1 \le c_i \le 10^9$

Жишээ

Оролт1

6 2
2 7 1 4 6 4

Гаралт1

0.1 / 64 KiB

Редактор уншиж байна...