← 返回题目列表

Codeforces · 2229/F

F. 负载不平衡

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

请注意异常低的时间限制。

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

您可以先根据需要重新排序 $$$a$$$ 的元素。然后,定义 $$$f(a)$$$ 如下:

  • 设 $$$b$$$ 为长度为 $$$k$$$ 的数组,最初全为零。
  • 对于每个 $$$1 \le i \le n$$$,将 $$$a_i$$$ 添加到 $$$b$$$ 的任何最小元素。
  • 在此过程结束时,$$$f(a) = \max(b)$$$。

找出 $$$f(a)$$$ 在 $$$a$$$ 的所有重新排列中的最大可能值。

输入

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

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le k \le n \le 18$$$)。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$)。

保证所有测试用例的$$$2^n$$$总和不超过$$$2^{18}$$$。

输出

对于每个测试用例,输出一个整数 - $$$f(a)$$$ 在 $$$a$$$ 的所有重新排列中的最大可能值。

示例

输入
复制

1
18 5
837492015 264819073 519603847 902746518 173058264 648291507 395174620 781532946 506847193 924613708 158397042 673029415 240785631 819456270 461302987 730619824 528947163 894271056

输出
复制

2823249283

输入
复制

6
4 2
1 2 4 5
1 1
10
8 3
3 4 1 3 2 4 5 3
3 1
1000000000 1000000000 1000000000
17 6
6 7 67 4 1 41 6 9 69 3 1 4 1 5 9 2 6
2 2
1 2

输出
复制

8
10
11
3000000000
85
2

注意

在第二个示例的第一个测试用例中,$$$a$$$ 的一个最佳重新排列是 $$$[1, 4, 2, 5]$$$。 $$$f(a)$$$ 计算如下:

$$$i$$$$$$a_i$$$$$$b$$$
$$$-$$$$$$-$$$$$$[0, 0]$$$
$$$1$$$$$$1$$$$$$[1, 0]$$$
$$$2$$$$$$4$$$$$$[1, 4]$$$
$$$3$$$$$$2$$$$$$[3, 4]$$$
$$$4$$$$$$5$$$$$$[8, 4]$$$

此后,$$$f(a) = \max([8,4]) = 8$$$。可以证明,可实现的最大值 $$$f(a)$$$ 为 $$$8$$$。

在第二个示例的第三个测试用例中,$$$a$$$ 的一个最佳重新排列是 $$$[3, 1, 2, 3, 5, 4, 3, 4]$$$。