2065D.md (2411B)
1 Source: https://codeforces.com/problemset/problem/2065/D 2 3 D. Skibidus and Sigma 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 Let's denote the score of an array $b$ with $k$ elements as $\sum_{i=1}^{k}\left(\sum_{j=1}^ib_j\right)$. In other words, let $S_i$ denote the sum of the first $i$ elements of $b$. Then, the score can be denoted as $S_1+S_2+\ldots+S_k$. 22 23 Skibidus is given $n$ arrays $a_1,a_2,\ldots,a_n$, each of which contains $m$ elements. Being the sigma that he is, he would like to concatenate them in any order to form a single array containing $n\cdot m$ elements. Please find the maximum possible score Skibidus can achieve with his concatenated array! 24 25 Formally, among all possible permutations$^{\text{∗}}$ $p$ of length $n$, output the maximum score of $a_{p_1} + a_{p_2} + \dots + a_{p_n}$, where $+$ represents concatenation$^{\text{†}}$. 26 27 $^{\text{∗}}$A permutation of length $n$ contains all integers from $1$ to $n$ exactly once. 28 29 $^{\text{†}}$The concatenation of two arrays $c$ and $d$ with lengths $e$ and $f$ respectively (i.e. $c + d$) is $c_1, c_2, \ldots, c_e, d_1, d_2, \ldots d_f$. 30 31 Input 32 33 The first line contains an integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. 34 35 The first line of each test case contains two integers $n$ and $m$ ($1 \leq n \cdot m \leq 2 \cdot 10^5$) — the number of arrays and the length of each array. 36 37 The $i$'th of the next $n$ lines contains $m$ integers $a_{i,1}, a_{i,2}, \ldots, a_{i,m}$ ($1 \leq a_{i,j} \leq 10^6$) — the elements of the $i$'th array. 38 39 It is guaranteed that the sum of $n \cdot m$ over all test cases does not exceed $2 \cdot 10^5$. 40 41 Output 42 43 For each test case, output the maximum score among all possible permutations $p$ on a new line. 44 45 Example 46 47 Input 48 49 ``` 50 3 51 52 2 2 53 54 4 4 55 56 6 1 57 58 3 4 59 60 2 2 2 2 61 62 3 2 1 2 63 64 4 1 2 1 65 66 2 3 67 68 3 4 5 69 70 1 1 9 71 ``` 72 73 Output 74 75 ``` 76 41 77 162 78 72 79 ``` 80 81 Note 82 83 For the first test case, there are two possibilities for $p$: 84 85 * $p = [1, 2]$. Then, $a_{p_1} + a_{p_2} = [4, 4, 6, 1]$. Its score is $4+(4+4)+(4+4+6)+(4+4+6+1)=41$. 86 * $p = [2, 1]$. Then, $a_{p_1} + a_{p_2} = [6, 1, 4, 4]$. Its score is $6+(6+1)+(6+1+4)+(6+1+4+4)=39$. 87 88 The maximum possible score is $41$. 89 90 In the second test case, one optimal arrangement of the final concatenated array is $[4,1,2,1,2,2,2,2,3,2,1,2]$. We can calculate that the score is $162$.