2158C.md (3347B)
1 Source: https://codeforces.com/problemset/problem/2158/C 2 3 C. Annoying Game 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 two integer arrays $a$ and $b$, both of length $n$, and a total number of turns $k$. 22 23 Alice and Bob play a game by taking turns modifying array $a$. Alice goes first. The game lasts for exactly $k$ turns. 24 25 On their turn, a player must choose an index $i$ ($1 \leq i \leq n$) and perform one of the following operations: 26 27 * Add: Increase $a_i$ by $b_i$, i.e., set $a_i := a_i + b_i$. 28 * Subtract: Decrease $a_i$ by $b_i$, i.e., set $a_i := a_i - b_i$. 29 30 After the $k$-th turn is complete, the final score is calculated as the maximum non-empty subarray sum of the modified array $a$. Alice's goal is to maximize the final score, while Bob's goal is to minimize the final score. 31 32 Assuming both players play optimally to achieve their respective goals, determine the final score. 33 34 The maximum non-empty subarray sum of $a$ is defined as $\max_{1 \leq i \leq j \leq n} S(i, j)$, where $S(i, j) = a_i + a_{i+1} + \cdots + a_j$. Note that empty subarrays are not considered. 35 36 Input 37 38 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. 39 40 The first line of each test case contains two integers $n$ and $k$ ($1 \le n \le 2\cdot 10^5$, $1 \le k \le 2\cdot 10^5$) — the length of the arrays and the total number of turns. 41 42 The second line contains $n$ integers $a_1,a_2,\ldots,a_{n}$ ($-10^9 \le a_i \le 10^9$) — the elements of array $a$. 43 44 The third line contains $n$ integers $b_1,b_2,\ldots,b_{n}$ ($0 \le b_i \le 10^9$) — the elements of array $b$. 45 46 It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$. 47 48 Output 49 50 For each test case, print a single integer — the final score after $k$ turns, assuming both players play optimally. 51 52 Example 53 54 Input 55 56 ``` 57 5 58 59 5 200000 60 61 3 -1 9 -5 4 62 63 0 0 0 0 0 64 65 4 5 66 67 10 10 10 10 68 69 1 1 1 1 70 71 3 1 72 73 2 -7 3 74 75 1 11 3 76 77 3 2 78 79 2 -7 3 80 81 1 11 3 82 83 1 1 84 85 -3 86 87 2 88 ``` 89 90 Output 91 92 ``` 93 11 94 95 41 96 97 9 98 99 3 100 101 -1 102 ``` 103 104 Note 105 106 For the first test case: 107 108 * Any move can't change the array $a$ because all elements in $b$ are zero. 109 * The maximum non-empty subarray sum of this final array is $3 + (-1) + 9 = 11$. 110 111 For the second test case, one of the possible optimal sequences of moves is: 112 113 * Alice adds $b_3=1$ to $a_3$. Array $a$ becomes $[10, 10, 11, 10]$. 114 * Bob subtracts $b_1=1$ from $a_1$. Array $a$ becomes $[9, 10, 11, 10]$. 115 * Alice adds $b_3=1$ to $a_3$. Array $a$ becomes $[9, 10, 12, 10]$. 116 * Bob subtracts $b_1=1$ from $a_1$. Array $a$ becomes $[8, 10, 12, 10]$. 117 * Alice adds $b_4=1$ to $a_4$. Array $a$ becomes $[8, 10, 12, 11]$. 118 * The maximum non-empty subarray sum of this final array is $8+10+12+11 = 41$. 119 120 For the third test case, one of the possible optimal sequences of moves is: 121 122 * Alice adds $b_2=11$ to $a_2$. Array $a$ becomes $[2, 4, 3]$. 123 * The maximum non-empty subarray sum of this final array is $2 + 4 + 3 = 9$. 124 125 For the fourth test case, one of the possible optimal sequences of moves is: 126 127 * Alice adds $b_2=11$ to $a_2$. Array $a$ becomes $[2, 4, 3]$. 128 * Bob subtracts $b_2=11$ from $a_2$. Array $a$ becomes $[2, -7, 3]$. 129 * The maximum non-empty subarray sum of this final array is $3$.