F - Plan Holidays Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 525 点

問題文

高橋君は N 日間のスケジュールを決めようとしています。初期状態ではどの日も休日ではありません。

以下のいずれかの操作を好きな回数繰り返すことができます。

  • 1 以上 N 以下の整数 i を選び、i 日目を休日にする。この操作にはコストが A_i かかる。
  • 2 以上 N-1 以下の整数 i のうち i-1 日目と i+1 日目がすでにどちらも休日であるような i を選び、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 日以上連続する休日を作ることができます。

  • 2 日目を一種類目の操作で休日にする。コストが 1 かかる。
  • 4 日目を一種類目の操作で休日にする。コストが 1 かかる。
  • 3 日目を二種類目の操作で休日にする。コストはかからない。

この操作方法のコストの総和は 2 です。コスト 2 未満で 2 日以上連続する休日を作ることはできないため、2 を出力してください。

Score : 525 points

Problem Statement

Takahashi is trying to decide his schedule for N days. Initially, none of the days are holidays.

He can repeat either of the following operations any number of times:

  • Choose an integer i between 1 and N, inclusive, and make day i a holiday. This operation costs A_i.
  • Choose an integer i between 2 and N-1, inclusive, such that both day i-1 and day i+1 are already holidays, and make day i a holiday. This operation is free.

Find the minimum total cost required to create a consecutive block of K or more holidays.

T test cases are given; solve each of them.

Constraints

  • 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
  • All input values are integers.
  • The sum of N over all test cases is at most 2\times 10^5.

Input

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

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

Here, \mathrm{case}_i denotes the input for the i-th test case. Each test case is given in the following format:

N K
A_1 A_2 \dots A_N

Output

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

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

Sample Output 1

2
29
1902064780

For the first test case, a consecutive block of at least two holidays can be created by performing operations as follows:

  • Make day 2 a holiday using the first type of operation. This costs 1.
  • Make day 4 a holiday using the first type of operation. This costs 1.
  • Make day 3 a holiday using the second type of operation. This is free.

The total cost of this sequence of operations is 2. It is impossible to create a consecutive block of two or more holidays with a cost less than 2, so output 2.