codeforces-scrape

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

1791E.md (2005B)


      1 Source: https://codeforces.com/problemset/problem/1791/E
      2 
      3 E. Negatives and Positives
      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 Given an array $a$ consisting of $n$ elements, find the maximum possible sum the array can have after performing the following operation any number of times:
     22 
     23 * Choose $2$ adjacent elements and flip both of their signs. In other words choose an index $i$ such that $1 \leq i \leq n - 1$ and assign $a_i = -a_i$ and $a_{i+1} = -a_{i+1}$.
     24 
     25 Input
     26 
     27 The input consists of multiple test cases. The first line contains an integer $t$ ($1 \leq t \leq 1000$) — the number of test cases. The descriptions of the test cases follow.
     28 
     29 The first line of each test case contains an integer $n$ ($2 \leq n \leq 2\cdot10^5$) — the length of the array.
     30 
     31 The following line contains $n$ space-separated integers $a_1,a_2,\dots,a_n$ ($-10^9 \leq a_i \leq 10^9$).
     32 
     33 It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot10^5$.
     34 
     35 Output
     36 
     37 For each test case, output the maximum possible sum the array can have after performing the described operation any number of times.
     38 
     39 Example
     40 
     41 Input
     42 
     43 ```
     44 5
     45 
     46 3
     47 
     48 -1 -1 -1
     49 
     50 5
     51 
     52 1 5 -5 0 2
     53 
     54 3
     55 
     56 1 2 3
     57 
     58 6
     59 
     60 -1 10 9 8 7 6
     61 
     62 2
     63 
     64 -1 -1
     65 ```
     66 
     67 Output
     68 
     69 ```
     70 1
     71 13
     72 6
     73 39
     74 2
     75 ```
     76 
     77 Note
     78 
     79 For the first test case, by performing the operation on the first two elements, we can change the array from $[-1, -1, -1]$ to $[1, 1, -1]$, and it can be proven this array obtains the maximum possible sum which is $1 + 1 + (-1) = 1$.
     80 
     81 For the second test case, by performing the operation on $-5$ and $0$, we change the array from $[1, 5, -5, 0, 2]$ to $[1, 5, -(-5), -0, 2] = [1, 5, 5, 0, 2]$, which has the maximum sum since all elements are non-negative. So, the answer is $1 + 5 + 5 + 0 + 2 = 13$.
     82 
     83 For the third test case, the array already contains only positive numbers, so performing operations is unnecessary. The answer is just the sum of the whole array, which is $1 + 2 + 3 = 6$.