/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
りんごさんは馬を縞模様に塗ってシマウマにしようとしています。
1 から N の番号がついた N 個のマスが一列に並んでいます。
最初、全てのマスは白色であり、マス i を黒く塗るためにはコストが C_i かかります。
以下の手順を一度だけ行い、いくつかのマスを黒く塗ることを考えます。
- 正整数 x を自由に選ぶ。
- 1 \leq i \leq N を満たす整数 i のうち、 (i+x) を 2W で割った余りが W より小さくなるもの全てに対し、マス i を黒く塗る。
この手順を行うためのコストの合計の最小値を求めてください。
T 個のテストケースが与えられるので、それぞれについて答えを求めてください。
制約
- 1\leq T \leq 2\times 10^5
- 1\leq N \leq 2\times 10^5
- 1\leq W \leq 2\times 10^5
- 1\leq C_i \leq 10^9
- T 個のテストケースにおける N の総和は 2\times 10^5 以下
- T 個のテストケースにおける W の総和は 2\times 10^5 以下
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。ここで \mathrm{case}_i は i 番目のテストケースを意味する。
T
\mathrm{case}_1
\vdots
\mathrm{case}_T
各テストケースは以下の形式で与えられる。
N W C_1 \dots C_N
出力
T 行出力せよ。i 行目には i 番目のテストケースに対する答えを出力せよ。
入力例 1
4 8 2 1 10 10 1 1 10 10 1 8 3 1 10 10 1 1 10 10 1 8 4 1 10 10 1 1 10 10 1 4 100 100000 100000 100000 100000
出力例 1
4 12 22 0
1 番目のテストケースにおいて、x=4 として手順を実行すると、マス 1,4,5,8 が黒く塗られ、コストの合計は 4 となります。 コストの合計を 4 未満にすることはできないため、これが最小値となります。
Score : 300 points
Problem Statement
Ringo-san is trying to paint a horse with stripes to make it a zebra.
There are N squares numbered 1 to N arranged in a line.
Initially, all squares are white, and the cost of painting square i black is C_i.
Consider performing the following procedure once to paint some squares black:
- Choose a positive integer x freely.
- Paint square i black for all integers i satisfying 1 \leq i \leq N such that the remainder when (i+x) is divided by 2W is less than W.
Find the minimum total cost to perform this procedure.
You are given T test cases; solve each of them.
Constraints
- 1\leq T \leq 2\times 10^5
- 1\leq N \leq 2\times 10^5
- 1\leq W \leq 2\times 10^5
- 1\leq C_i \leq 10^9
- The sum of N over the T test cases is at most 2\times 10^5.
- The sum of W over the T test cases is at most 2\times 10^5.
- All input values are integers.
Input
The input is given from Standard Input in the following format, where \mathrm{case}_i denotes the i-th test case.
T
\mathrm{case}_1
\vdots
\mathrm{case}_T
Each test case is given in the following format:
N W C_1 \dots C_N
Output
Output T lines. The i-th line should contain the answer for the i-th test case.
Sample Input 1
4 8 2 1 10 10 1 1 10 10 1 8 3 1 10 10 1 1 10 10 1 8 4 1 10 10 1 1 10 10 1 4 100 100000 100000 100000 100000
Sample Output 1
4 12 22 0
In the first test case, if the procedure is executed with x=4, squares 1,4,5,8 are painted black, and the total cost is 4. The total cost cannot be less than 4, so this is the minimum.