CF2239B Decidophobia

There are $ n $ people attending a round-table party, numbered $ 1, 2, 3, \ldots, n $ in clockwise order. You have prepared some gifts to distribute among them. Each person $ i $ has a weight $ a_i $ and a common field of view $ d $ . The field of view for person $ i $ consists of the $ d $ people sitting clockwise and the $ d $ people sitting counter-clockwise from them (a total of $ 2d $ people excluding person $ i $ ). The happiness gained by person $ i $ is determined by the following rules: - If person $ i $ receives a gift, and there are $ x $ people within their field of view who did not receive a gift, they gain $ x \cdot a_i $ happiness. - If person $ i $ does not receive a gift, and there are $ x $ people within their field of view who received a gift, they incur $ -x \cdot a_i $ happiness. You want to maximize the total happiness of all $ n $ people combined. Find this maximum value.

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows. The first line of each test case contains two integers $ n $ and $ d $ ( $ 3 \le n \le 2 \cdot 10^5 $ , $ 1 \le d \lt \frac{n}{2} $ ). The second line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le 10^8 $ ), where $ a_i $ is the weight of the $ i $ -th person. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 10^6 $ .

For each test case, output a single integer representing the maximum total happiness.

In the first test case, there are 3 people sitting in a circle. For each person $ i $ , the field of view is $ d=1 $ , which includes the 1 person sitting clockwise and the 1 person sitting counter-clockwise from them. If person 2 receives the gift, they gain happiness from 2 neighbors who did not receive it, resulting in $ 2 \cdot a_2 = 2 \cdot 2 = 4 $ . However, person 1 and person 3 incur loss because they did not receive a gift but have a neighbor who did. After calculating all possibilities, the maximum total happiness is 3. In the second test case, $ n=5, d=1 $ . The best solution is to give gifts to persons 2, 3, and 5, which can achieve the maximum total happiness value of 15.