2140C.md (2108B)
1 Source: https://codeforces.com/problemset/problem/2140/C 2 3 C. Ultimate Value 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 Let's define a function $f(a)$ for an array $a$ of length $n$ as $$f(a) = \textrm{cost} + (a_1 - a_2 + a_3 - a_4 \cdots a_n)$$ where $\textrm{cost}$ is zero initially. 22 23 Now consider the scenario where Alice and Bob are given an array $a$ of length $n$. They play a game taking at most $10^{100}$ turns alternately with Alice going first. 24 25 In each turn, they must perform any one (only one) of the following operations: 26 27 * End the game for both Alice and Bob. 28 * Choose two indices $l,r$ with $1 \le l \le r \le n$ and swap $a_l$ and $a_r$; this adds $(r - l)$ to the $\textrm{cost}$. 29 30 Assume that Alice tries to maximize $f(a)$ and Bob tries to minimize it. 31 32 Your task is to determine the final value of $f(a)$ assuming both players play optimally. 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 a single integer $n$ ($1 \le n \le 2\cdot10^5$) — the length of the array $a$. 39 40 The second line contains $n$ integers $a_1,a_2,a_3,\ldots,a_n$ ($1 \le a_i \le 10^9$) — the elements of the array $a$. 41 42 It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot10^5$. 43 44 Output 45 46 For each testcase, output a single integer — the final value of $f(a)$ assuming both players play optimally. 47 48 Example 49 50 Input 51 52 ``` 53 5 54 55 2 56 57 1000 1 58 59 5 60 61 9 9 9 9 9 62 63 4 64 65 7 1 8 4 66 67 6 68 69 1 14 1 14 1 15 70 71 9 72 73 31 12 14 22 89 6 78 25 91 74 ``` 75 76 Output 77 78 ``` 79 999 80 13 81 12 82 -7 83 265 84 ``` 85 86 Note 87 88 For the first testcase, it is optimal for Alice to end the game on her first turn. 89 90 So the final value of $\textrm{cost} = 0$ and $f(a) = 0 + 1000 - 1 = 999$. 91 92 For the fourth testcase, it is optimal for Alice to swap $a_1$ and $a_6$, and then it is optimal for Bob to end the game on his first turn. 93 94 So the final value of $\textrm{cost} = 5$ and $f(a) = 5 + 15 - 14 + 1 - 14 + 1 - 1=-7$.