分数: 475 点
问题陈述
给定长度序列 N: A = (A_1, A_2, \dots, A_N) 和 B = (B_1, B_2, \dots, B_N).
让 S 是以下子集 \lbrace1, 2, \dots, N\rbrace 尺寸 K。
在这里,找到以下表达式的最小可能值:
\displaystyle \left(\max_{i \in S} A_i\right) \times \left(\sum_{i \in S} B_i\right).
你被给予 T 测试用例;解决它们中的每一个。
约束
- 1 \leq T \leq 2 \times 10^5
- 1 \leq K \leq N \leq 2 \times 10^5
- 1 \leq A_i, B_i \leq 10^6
- 总和 N 所有测试用例最多 2 \times 10^5.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出。在这里, \mathrm{case}_i 表示 i- 第一个测试用例。
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
每个测试用例均按以下格式给出:
N K A_1 A_2 \dots A_N B_1 B_2 \dots B_N
输出
打印 T 行。的 i- 第行应包含以下问题的答案 i- 第一个测试用例。
示例输入 1
3 3 2 3 7 6 9 2 4 5 3 6 4 1 5 9 8 6 5 1 7 10 6 61 95 61 57 69 49 46 47 14 43 39 79 48 92 90 76 30 16 30 94
示例输出 1
42 60 14579
在第一个测试用例中,对于 S = \{2, 3\},表达式的值为 7 \times (2 + 4) = 42,这是最小值。