codeforces-scrape

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

1447B.md (1735B)


      1 Source: https://codeforces.com/problemset/problem/1447/B
      2 
      3 B. Numbers Box
      4 
      5 time limit per test
      6 
      7 1 second
      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 a rectangular grid with $n$ rows and $m$ columns. The cell located on the $i$-th row from the top and the $j$-th column from the left has a value $a_{ij}$ written in it.
     22 
     23 You can perform the following operation any number of times (possibly zero):
     24 
     25 * Choose any two adjacent cells and multiply the values in them by $-1$. Two cells are called adjacent if they share a side.
     26 
     27 Note that you can use a cell more than once in different operations.
     28 
     29 You are interested in $X$, the sum of all the numbers in the grid.
     30 
     31 What is the maximum $X$ you can achieve with these operations?
     32 
     33 Input
     34 
     35 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 100$). Description of the test cases follows.
     36 
     37 The first line of each test case contains two integers $n$,$m$ ($2 \le n$, $m \le 10$).
     38 
     39 The following $n$ lines contain $m$ integers each, the $j$-th element in the $i$-th line is $a_{ij}$ ($-100\leq a_{ij}\le 100$).
     40 
     41 Output
     42 
     43 For each testcase, print one integer $X$, the maximum possible sum of all the values in the grid after applying the operation as many times as you want.
     44 
     45 Example
     46 
     47 Input
     48 
     49 ```
     50 2
     51 2 2
     52 -1 1
     53 1 1
     54 3 4
     55 0 -1 -2 -3
     56 -1 -2 -3 -4
     57 -2 -3 -4 -5
     58 ```
     59 
     60 Output
     61 
     62 ```
     63 2
     64 30
     65 ```
     66 
     67 Note
     68 
     69 In the first test case, there will always be at least one $-1$, so the answer is $2$.
     70 
     71 In the second test case, we can use the operation six times to elements adjacent horizontally and get all numbers to be non-negative. So the answer is: $2\times 1 + 3\times2 + 3\times 3 + 2\times 4 + 1\times 5 = 30$.