codeforces-scrape

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

1825B.md (2755B)


      1 Source: https://codeforces.com/problemset/problem/1825/B
      2 
      3 B. LuoTianyi and the Table
      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 LuoTianyi gave an array $b$ of $n \cdot m$ integers. She asks you to construct a table $a$ of size $n \times m$, filled with these $n \cdot m$ numbers, and each element of the array must be used exactly once. Also she asked you to maximize the following value:
     22 
     23  $\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\left(\max\limits_{1 \le x \le i, 1 \le y \le j}a_{x,y}-\min\limits_{1 \le x \le i, 1 \le y \le j}a_{x,y}\right)$ 
     24 
     25 This means that we consider $n \cdot m$ subtables with the upper left corner in $(1,1)$ and the bottom right corner in $(i, j)$ ($1 \le i \le n$, $1 \le j \le m$), for each such subtable calculate the difference of the maximum and minimum elements in it, then sum up all these differences. You should maximize the resulting sum.
     26 
     27 Help her find the maximal possible value, you don't need to reconstruct the table itself.
     28 
     29 Input
     30 
     31 Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 200$) — the number of test cases. The description of test cases follows.
     32 
     33 The first line of each test case contains two integers $n$ and $m$ ($2 \le n, m \le 100$) — the number of rows and columns of the table.
     34 
     35 The second line of each test case contains $n \cdot m$ integers $b_1, b_2, \ldots, b_{n\cdot m}$ ($-10^5 \le b_{i} \le 10^5$) — the numbers you can put in the table.
     36 
     37 Note, that integers in the array $b$ can be negative.
     38 
     39 It is guaranteed that the sum of $n \cdot m$ over all test cases doesn't exceed $2\cdot 10^5$.
     40 
     41 Output
     42 
     43 For each test case, output a single integer — the maximal value, that can be obtained.
     44 
     45 Example
     46 
     47 Input
     48 
     49 ```
     50 5
     51 
     52 2 2
     53 
     54 1 3 1 4
     55 
     56 2 2
     57 
     58 -1 -1 -1 -1
     59 
     60 2 3
     61 
     62 7 8 9 -3 10 8
     63 
     64 3 2
     65 
     66 4 8 -3 0 -7 1
     67 
     68 4 3
     69 
     70 -32030 59554 16854 -85927 68060 -64460 -79547 90932 85063 82703 -12001 38762
     71 ```
     72 
     73 Output
     74 
     75 ```
     76 9
     77 0
     78 64
     79 71
     80 1933711
     81 ```
     82 
     83 Note
     84 
     85 In the first test case, the table is follows:
     86 
     87 |  |  |
     88 | --- | --- |
     89 | 4 | 1 |
     90 | 1 | 3 |
     91 
     92 In the subtable with the bottom right corner in $(1, 1)$, the difference of the maximal and minimal elements is $4 - 4 = 0$.
     93 
     94 In the subtable with the bottom right corner in $(1, 2)$, the difference of the maximal and minimal elements is $4 - 1 = 3$.
     95 
     96 In the subtable with the bottom right corner in $(2, 1)$, the difference of the maximal and minimal elements is $4 - 1 = 3$.
     97 
     98 In the subtable with the bottom right corner in $(2, 2)$, the difference of the maximal and minimal elements is $4 - 1 = 3$.
     99 
    100 Then the maximum possible value is $0+3+3+3=9$.
    101 
    102 In the second test case, all elements are equal, so all differences are $0$, and the answer is $0$.