2268A.md (1976B)
1 Source: https://codeforces.com/problemset/problem/2268/A 2 3 A. K Is Important 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You are given an array $a$ consisting of $n$ positive integers, as well as an integer parameter $k$. 22 23 While the array has at least $k$ elements, you need to perform one of the following two types of operations on $a$: 24 25 * Remove $a_k$ and add its value to your score, or 26 * Remove $a_{m-k+1}$ and add its value to your score, where $m$ is the length of $a$ before this operation. 27 28 After removing an element, the remaining elements keep their relative order. 29 30 Your task is to determine the maximum possible score that can be obtained. 31 32 Input 33 34 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. 35 36 The first line of each test case contains two integers $n$ and $k$ ($1 \le k \le n \le 10^5$) — the length of $a$ and the parameter. 37 38 The second line contains $n$ integers $a_i$ ($1 \le a_i \le 10^9$) — the elements of $a$. 39 40 It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$. 41 42 Output 43 44 For each test case, output a single integer — the maximum score that can be obtained. 45 46 Example 47 48 Input 49 50 ``` 51 4 52 53 4 2 54 55 1 2 3 4 56 57 4 4 58 59 3 4 1 2 60 61 1 1 62 63 1 64 65 6 3 66 67 1 4 8 2 6 3 68 ``` 69 70 Output 71 72 ``` 73 9 74 75 3 76 77 1 78 79 19 80 ``` 81 82 Note 83 84 In the first test case, we can first remove $a_3 = 3$. The score becomes $3$, and the array becomes $[1, 2, 4]$. Then we remove $a_2 = 2$, so the score becomes $5$, and the array becomes $[1, 4]$. Finally, we remove $a_2 = 4$, and the score becomes $9$. Now the length of the array is less than $k=2$, so no more operations can be performed. It can be proven that the maximum score is $9$. 85 86 In the second test case, we can only perform one operation, either removing $a_1 = 3$ or $a_4 = 2$. Obviously, it is better to remove $a_1 = 3$ to get a score of $3$.