codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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$.