codeforces-scrape

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

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