codeforces-scrape

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

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