2178C.md (2858B)
1 Source: https://codeforces.com/problemset/problem/2178/C 2 3 C. First or Second 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 There are $n$ children standing in a line, where the niceness of the $i$-th child is $a_i$. Santa is deciding which children belong on the nice list and which belong on the naughty list. 22 23 An integer $X$ is initially set to $0$. Santa will perform the following operation exactly $n-1$ times: 24 25 * Choose the first or second child in line and remove them from the line. 26 * Let $w$ be the niceness of the chosen child. 27 + If the first child was chosen, add them to the nice list and add $w$ to $X$. 28 + If the second child was chosen, add them to the naughty list and subtract $w$ from $X$. 29 30 Note that after all operations, exactly one child remains unassigned to a list. 31 32 Determine the maximum possible value of $X$ that Santa can obtain after all $n-1$ operations. 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$ ($2\le n\le 2\cdot 10^5$) — the number of children. 39 40 The second line contains $n$ integers $a_1,a_2,\ldots,a_n$ ($-10^9\le a_i\le 10^9$) — the niceness of each child. 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, print a single integer — the maximum possible value of $X$ that Santa can obtain after all $n-1$ operations. 47 48 Example 49 50 Input 51 52 ``` 53 7 54 55 2 56 57 2 -3 58 59 4 60 61 1 4 3 4 62 63 4 64 65 -4 2 3 -6 66 67 5 68 69 -2 -3 4 10 -9 70 71 5 72 73 -12345678 -1000000000 -999999999 1000000000 -999999999 74 75 2 76 77 -7 1 78 79 5 80 81 7 -6 -1 -8 -8 82 ``` 83 84 Output 85 86 ``` 87 3 88 89 8 90 91 4 92 93 15 94 95 2987654321 96 97 -1 98 99 29 100 ``` 101 102 Note 103 104 In the first test case, Santa will perform exactly one operation. If he chooses the first child, he will add $a_1=2$ to $X$ to get $X=2$; if he chooses the second child, he will subtract $a_2=-3$ from $X$ to get $X=3$. Thus, the answer is $3$. 105 106 In the second test case, it is optimal to select the first child in all three operations. The value of $X$ will be $1+4+3=8$. 107 108 In the third test case, below is an optimal sequence of operations: 109 110 | | | | | 111 | --- | --- | --- | --- | 112 | # | Type | Niceness of remaining children | $X$ after operation | 113 | 0 | — | $[-4, 2, 3, -6]$ | $0$ | 114 | 1 | First | $[2, 3, -6]$ | $-4$ | 115 | 2 | First | $[3, -6]$ | $-2$ | 116 | 3 | Second | $[3]$ | $4$ | 117 118 In the fourth test case, below is an optimal sequence of operations: 119 120 | | | | | 121 | --- | --- | --- | --- | 122 | # | Type | Niceness of remaining children | $X$ after operation | 123 | 0 | — | $[-2, -3, 4, 10, -9]$ | $0$ | 124 | 1 | Second | $[-2, 4, 10, -9]$ | $3$ | 125 | 2 | First | $[4, 10, -9]$ | $1$ | 126 | 3 | First | $[10, -9]$ | $5$ | 127 | 4 | First | $[-9]$ | $15$ |