← 返回题目列表

Codeforces · 2183/H

H. 最小化成本

中文机器翻译题面 查看原题

对于任何长度为 $$$m$$$ 的序列 $$$b$$$,我们将其成本函数 $$$f(b)$$$ 定义为: $$f(b) = m \cdot \sum_{i=1}^m b_i.$$

给定一个长度为 $$$n$$$ 的序列 $$$a$$$ 和一个整数 $$$k$$$。

你的任务是将序列 $$$a$$$ 划分为 正是 $$$k$$$ 非空子序列$$$^{\text{*}}$$$,表示为$$$s_1、s_2、\ldots、s_k$$$。原始序列 $$$a$$$ 的每个元素都必须恰好属于这些子序列之一。

求总成本的最小可能值:$$\sum_{i=1}^k f(s_i).$$

$$$^{\text{*}}$$$ 序列 $$$c$$$ 是序列 $$$d$$$ 的子序列,如果 $$$c$$$ 可以通过从任意位置删除几个(可能是零个或全部)元素从 $$$d$$$ 获得。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1\le k\le n \le 2\cdot 10^5$$$) — 序列的长度和所需子序列的数量。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$\mathbf{-10^9} \le a_i \le \mathbf{10^9}$$$) — 序列 $$$a$$$ 的元素。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot 10^5$$$。

输出

对于每个测试用例,输出一个整数——所有子序列的最小成本总和。

示例

输入
复制

6
3 2
1 3 -2
3 1
1 3 -2
10 4
-4 -6 -8 6 -3 -7 -3 1 6 -5
10 9
1 -2 6 -2 -6 4 3 3 7 -1
20 5
-5 9 -4 10 -2 4 -1 3 5 6 7 9 8 1 0 -6 4 5 8 9
50 26
7 10 10 2 2 1 7 4 4 8 5 8 -10 6 1 4 7 8 0 0 -8 1 1 5 0 0 6 0 7 4 6 0 7 4 -2 0 0 8 1 4 -7 0 6 -9 4 10 8 2 0 9

输出
复制

1
6
-239
5
131
-404

注意

在第一个测试用例中,最好拆分为 $$$[1,-2]$$$ 和 $$$[3]$$$。总分是$$$2(1-2)+1(3)=1$$$。

在第二个测试用例中,唯一可能的分区方法是使用 $$$1$$$ 子序列 $$$[1,3,-2]$$$。得分为$$$3(1+3-2)=6$$$。