CF1175D Array Splitting

给定一个数组 $a_1, a_2, \dots, a_n$ 和一个整数 $k$。 你需要将该数组划分为 $k$ 个非空连续子数组。数组中的每个元素必须且仅属于一个子数组。设 $f(i)$ 表示第 $i$ 个元素属于的子数组编号。子数组从左到右编号，编号为 $1$ 到 $k$。 划分的代价定义为 $\sum\limits_{i=1}^{n} (a_i \cdot f(i))$。例如，如果 $a = [1, -2, -3, 4, -5, 6, -7]$，将其划分为 $3$ 个子数组，方式为 $[1, -2, -3], [4, -5], [6, -7]$，则划分代价为 $1 \cdot 1 - 2 \cdot 1 - 3 \cdot 1 + 4 \cdot 2 - 5 \cdot 2 + 6 \cdot 3 - 7 \cdot 3 = -9$。 请计算将数组 $a$ 划分为 $k$ 个非空连续子数组所能获得的最大代价。

第一行包含两个整数 $n$ 和 $k$（$1 \le k \le n \le 3 \times 10^5$）。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$|a_i| \le 10^6$）。

输出将数组 $a$ 划分为 $k$ 个非空连续子数组所能获得的最大代价。

由 ChatGPT 4.1 翻译