← 返回题目列表

AtCoder · agc071_d

D. K 级术语

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

分数: 1300 点

问题陈述

给你整数 N, K,以及长度-N 非负整数序列 A = (A_1, A_2, \dots, A_N).

A 是单调非递减序列。也就是说, A_i \leq A_{i+1} 适用于所有人 i = 1, 2, \dots, N - 1.

我们称长度为N 非负整数序列 X = (X_1, X_2, \dots, X_N) 一个“好的序列”如果 X 是单调非递减的,可以使 X 等于 0 通过应用以下操作零次或多次:

  • 选择一个整数 i 这样 1 \leq i \leq N - K + 1。让 S = X_i + X_{i+1} + \dots + X_{i+K-1}。更换每个 i-th 通过 此时的第 (i+K-1)第一个元素 X 与 \left\lfloor \frac{S}{K} \right\rfloor.

找到最大可能值 \sum_{i=1}^N B_i 用于非负整数序列 B = (B_1, B_2, \dots, B_N) 满足以下所有条件:

  • B_i \leq A_i 适用于所有人 i = 1, 2, \dots, N.
  • B 是一个单调非递减序列,并且是一个“好序列”。

你有 T 测试用例;解决它们中的每一个。

约束

  • 1 \leq T \leq 10^5
  • 2 \leq K \leq N \leq 2 \times 10^5
  • 0 \leq A_i \leq 10^{9}
  • A_i \leq A_{i+1} 适用于所有人 i = 1, 2, \dots, N - 1.
  • 所有输入值均为整数。
  • 总和 N 一个输入中的所有测试用例最多 2 \times 10^5.

输入

输入由标准输入按以下格式给出:

T
\mathrm{case}_1
\vdots
\mathrm{case}_T

每个案例均按以下格式给出:

N K
A_1 A_2 \dots A_N

输出

打印 T 行。的 i- 第行应包含以下问题的答案 i- 第一个测试用例。


示例输入 1

4
4 2
0 1 2 3
4 3
0 1 2 3
20 5
1 2 3 3 4 5 6 7 7 8 9 9 11 13 14 16 16 17 18 19
20 10
36410986 135774405 160873759 200077345 386257217 408140905 426675713 448759426 470780343 572969565 653981029 693304642 741916215 764524315 768298046 811893935 840607643 847634785 856942510 883746061

示例输出 1

6
5
185
739

在第一个测试用例中, A 本身就是一个“好的序列”。例如,我们可以将所有元素 A 等于 0 执行以下步骤:

  1. 让 i=3。然后, S=A_3+A_4=5。更换 A_3 和 A_4 与 \left\lfloor \frac{5}{2} \right\rfloor = 2,导致 A=(0,1,2,2).
  2. 让 i=2。然后, S=A_2+A_3=3。更换 A_2 和 A_3 与 \left\lfloor \frac{3}{2} \right\rfloor = 1,导致 A=(0,1,1,2).
  3. 让 i=3。然后, S=A_3+A_4=3。更换 A_3 和 A_4 与 \left\lfloor \frac{3}{2} \right\rfloor = 1,导致 A=(0,1,1,1).
  4. 让 i=1。然后, S=A_1+A_2=1。更换 A_1 和 A_2 与 \left\lfloor \frac{1}{2} \right\rfloor = 0,导致 A=(0,0,1,1).
  5. 让 i=2。然后, S=A_2+A_3=1。更换 A_2 和 A_3 与 \left\lfloor \frac{1}{2} \right\rfloor = 0,导致 A=(0,0,0,1).
  6. 让 i=3。然后, S=A_3+A_4=1。更换 A_3 和 A_4 与 \left\lfloor \frac{1}{2} \right\rfloor = 0,导致 A=(0,0,0,0).

因此,采取 B = A 达到最大总和 0+1+2+3=6.

在第二个测试用例中, A 不是一个“好的序列”。然而,如果我们采取 B = (0,0,2,3),那么 B 是一个“好序列”并且满足条件。