分数: 525 点
问题陈述
高桥正在努力决定他的日程 N 天。最初,没有一天是假期。
他可以重复以下任一操作任意次数:
- 选择一个整数 i 之间 1 和 N,包含在内,并让日子 i 放假。此操作成本 A_i.
- 选择一个整数 i 之间 2 和 N-1,包含在内,这样两天 i-1 和日 i+1 已经是假期了,让一天 i 放假。此操作是免费的。
找出创建连续块所需的最小总成本 K 或更多假期。
T 给出了测试用例;解决它们中的每一个。
约束
- 1 \leq T \leq 2 \times 10^5
- 1 \leq K \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9
- 所有输入值均为整数。
- 总和 N 所有测试用例最多 2\times 10^5.
输入
输入由标准输入按以下格式给出:
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
在这里, \mathrm{case}_i 表示输入 i- 第一个测试用例。每个测试用例均按以下格式给出:
N K A_1 A_2 \dots A_N
输出
输出 T 行。的 i- 第行应包含以下问题的答案 i- 第一个测试用例。
示例输入 1
3 5 2 3 1 4 1 5 6 4 24 3 22 39 4 29 15 7 220651272 302798780 874479994 657822311 613294668 479624013 241168404 610547619 762548286 256160531 823041612 951553052 226556081 649525901 153805947
示例输出 1
2 29 1902064780
对于第一个测试用例,可以通过执行以下操作来创建至少两个假期的连续块:
- 创造一天 2 节假日使用第一种操作方式。这需要花费 1.
- 创造一天 4 节假日使用第一种操作方式。这需要花费 1.
- 创造一天 3 节假日使用第二种操作方式。这是免费的。
这一系列操作的总成本是 2。不可能以低于以下的成本创建两个或多个假期的连续块 2,所以输出 2.