D - Level K Terms Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 1300 点

問題文

整数 N,K および長さ N の非負整数列 A=(A_1,A_2,\dots,A_N) が与えられます。

A は単調非減少列です。すなわち、 i=1,2,\dots,N-1 に対して A_i \leq A_{i+1} が成り立ちます。

長さ N の単調非減少列である非負整数列 X=(X_1,X_2,\dots,X_N) に対して以下の操作を 0 回以上行うことで X の全ての項の値を 0 にできるとき、 X は「良い数列」であるといいます。

  • 1 \leq i \leq N-K+1 を満たす整数 i を選ぶ。 S=X_i+X_{i+1}+\dots +X_{i+K-1} とする。 X の i,i+1,\dots,i+K-1 項目の値を全て \left\lfloor \frac{S}{K}\right\rfloor で置き換える。

以下の条件をすべて満たす非負整数列 B=(B_1,B_2,\dots,B_N) に対する \sum_{i=1}^N B_i の最大値を求めてください。

  • i=1,2,\dots,N に対し、 B_i \leq A_i が成り立つ。
  • 非負整数列 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}
  • i=1,2,\dots,N-1 に対して A_i \leq A_{i+1} が成り立つ
  • 入力される値はすべて整数
  • 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

1 番目のテストケースについて、 A は「良い数列」になっています。これについて、例えば操作を以下の手順で行うことで A の全ての項の値を 0 にできます。

  1. i=3 とする。 S=A_3+A_4=5 となり、 A の 3,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,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,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,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,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,4 項目の値は \left\lfloor \frac{1}{2}\right \rfloor = 0 に置き換えられ、 A=(0,0,0,0) となる。

よって B=A とすることで最大値 0+1+2+3=6 を達成します。

2 番目のテストケースについて、 A は「良い数列」ではありません。 B=(0,0,2,3) とすると B は「良い数列」であり、条件を満たします。

Score : 1300 points

Problem Statement

You are given integers N, K, and a length-N sequence of non-negative integers A = (A_1, A_2, \dots, A_N).

A is a monotonically non-decreasing sequence. That is, A_i \leq A_{i+1} holds for all i = 1, 2, \dots, N - 1.

We call a length-N sequence of non-negative integers X = (X_1, X_2, \dots, X_N) a "good sequence" if X is monotonically non-decreasing and one can make all elements of X equal to 0 by applying the following operation zero or more times:

  • Choose an integer i such that 1 \leq i \leq N - K + 1. Let S = X_i + X_{i+1} + \dots + X_{i+K-1}. Replace each of the i-th through (i+K-1)-th elements of X with \left\lfloor \frac{S}{K} \right\rfloor.

Find the maximum possible value of \sum_{i=1}^N B_i for a sequence of non-negative integers B = (B_1, B_2, \dots, B_N) that satisfy all of the following conditions:

  • B_i \leq A_i holds for all i = 1, 2, \dots, N.
  • B is a monotonically non-decreasing sequence and is a "good sequence."

You have T test cases; solve each of them.

Constraints

  • 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} holds for all i = 1, 2, \dots, N - 1.
  • All input values are integers.
  • The sum of N over all test cases in one input is at most 2 \times 10^5.

Input

The input is given from Standard Input in the following format:

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

Each case is given in the following format:

N K
A_1 A_2 \dots A_N

Output

Print T lines. The i-th line should contain the answer for the i-th test case.

Sample Input 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

Sample Output 1

6
5
185
739

In the first test case, A itself is a "good sequence." For example, we can make all elements of A equal to 0 with the following steps:

  1. Let i=3. Then, S=A_3+A_4=5. Replace A_3 and A_4 with \left\lfloor \frac{5}{2} \right\rfloor = 2, resulting in A=(0,1,2,2).
  2. Let i=2. Then, S=A_2+A_3=3. Replace A_2 and A_3 with \left\lfloor \frac{3}{2} \right\rfloor = 1, resulting in A=(0,1,1,2).
  3. Let i=3. Then, S=A_3+A_4=3. Replace A_3 and A_4 with \left\lfloor \frac{3}{2} \right\rfloor = 1, resulting in A=(0,1,1,1).
  4. Let i=1. Then, S=A_1+A_2=1. Replace A_1 and A_2 with \left\lfloor \frac{1}{2} \right\rfloor = 0, resulting in A=(0,0,1,1).
  5. Let i=2. Then, S=A_2+A_3=1. Replace A_2 and A_3 with \left\lfloor \frac{1}{2} \right\rfloor = 0, resulting in A=(0,0,0,1).
  6. Let i=3. Then, S=A_3+A_4=1. Replace A_3 and A_4 with \left\lfloor \frac{1}{2} \right\rfloor = 0, resulting in A=(0,0,0,0).

Thus, taking B = A achieves the maximum sum 0+1+2+3=6.

In the second test case, A is not a "good sequence." However, if we take B = (0,0,2,3), then B is a "good sequence" and satisfies the conditions.