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

板块: Advanced Techniques

时限: 1.00 s ｜ 内存: 512 MB

题目描述

一条街道上有 $n$ 栋房屋，编号为 $1,2,\dots,n$。房屋 $a$ 与房屋 $b$ 之间的距离为 $|a-b|$。你知道每栋房屋中孩子的数量。

你的任务是建立 $k$ 所学校，每所学校都建在某栋房屋处。之后，每个孩子前往离自己最近的学校。在最优化的情况下，孩子们行走的总距离最小是多少？

输入

第一行有两个整数 $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$

样例输入

6 2
2 7 1 4 6 4

样例输出

11