2245B.md (2538B)
1 Source: https://codeforces.com/problemset/problem/2245/B 2 3 B. Delete and Concatenate 4 5 time limit per test 6 7 1.5 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$ of $n$ integers. Your initial score is $0$. 22 23 You can perform the following two types of operations any number of times until the array becomes empty: 24 25 * Choose a single element. Add its value to your score, and remove it from the array. 26 * Choose two adjacent elements. Add the maximum of their values to your score, and remove both elements from the array. (This operation requires the array to have at least $2$ elements.) 27 28 After each operation, the remaining elements are concatenated without changing their relative order. 29 30 You are also given an integer $c$, which represents the cost of performing one operation. Every time you perform an operation (regardless of the type), $c$ is subtracted from your score. 31 32 Compute the maximum possible final score you can achieve. 33 34 Input 35 36 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. 37 38 The first line of each test case contains two integers $n$ and $c$ ($1 \le n \le 2 \cdot 10^5$, $0 \le c \le 10^9$), representing the length of $a$ and the cost of performing one operation, respectively. 39 40 The second line contains $n$ integers $a_1,a_2,\ldots,a_n$ ($-10^9 \le a_i \le 10^9$), representing the elements of $a$. 41 42 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. 43 44 Output 45 46 For each test case, output an integer representing the maximum possible score you can achieve. 47 48 Example 49 50 Input 51 52 ``` 53 5 54 55 1 0 56 57 -1 58 59 3 0 60 61 1 3 1 62 63 3 2 64 65 1 3 1 66 67 6 6 68 69 3 1 4 1 5 9 70 71 4 1000000000 72 73 -1000000000 -1000000000 -1000000000 -1000000000 74 ``` 75 76 Output 77 78 ``` 79 -1 80 81 5 82 83 0 84 85 0 86 87 -4000000000 88 ``` 89 90 Note 91 92 In the first test case, your only possible choice is to perform the first operation once. Your score is $a_1-c=-1-0=-1$. 93 94 In the second test case, one optimal sequence of operations is: 95 96 * Choose $3$. Your score becomes $0+3-0=3$, and the array becomes $[1,1]$. 97 * Choose the first $1$. Your score becomes $3+1-0=4$, and the array becomes $[1]$. 98 * Choose $1$. Your score becomes $4+1-0=5$, and the array becomes empty. 99 100 In the third test case, one optimal sequence of operations is: 101 102 * Choose $3$ and the second $1$. Your score becomes $0+\max(3,1)-2=1$, and the array becomes $[1]$. 103 * Choose $1$. Your score becomes $1+1-2=0$, and the array becomes empty.