codeforces-scrape

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

2000E.md (2351B)


      1 Source: https://codeforces.com/problemset/problem/2000/E
      2 
      3 E. Photoshoot for Gorillas
      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 You really love gorillas, so you decided to organize a photoshoot for them. Gorillas live in the jungle. The jungle is represented as a grid of $n$ rows and $m$ columns. $w$ gorillas agreed to participate in the photoshoot, and the gorilla with index $i$ ($1 \le i \le w$) has a height of $a_i$. You want to place all the gorillas in the cells of the grid such that there is no more than one gorilla in each cell.
     22 
     23 The spectacle of the arrangement is equal to the sum of the spectacles of all sub-squares of the grid with a side length of $k$.
     24 
     25 The spectacle of a sub-square is equal to the sum of the heights of the gorillas in it.
     26 
     27 From all suitable arrangements, choose the arrangement with the maximum spectacle.
     28 
     29 Input
     30 
     31 The first line contains an integer $t$ ($1 \le t \le 10^3$) — the number of test cases.
     32 
     33 The descriptions of the test cases follow.
     34 
     35 The first line contains integers $n$, $m$, $k$ ($1 \le n, m \le 2 \cdot 10^5$, $1 \le n \cdot m \le 2 \cdot 10^5$, $1 \le k \le \min(n, m)$) — the dimensions of the grid and the side length of the square.
     36 
     37 The second line contains an integer $w$ ($1 \le w \le n \cdot m$) — the number of gorillas.
     38 
     39 The third line contains $w$ integers $a_1, a_2, \ldots, a_w$ ($1 \le a_i \le 10^9$) — the heights of the gorillas.
     40 
     41 It is guaranteed that the sum of $n \cdot m$ across all test cases does not exceed $2 \cdot 10^5$. The same guarantee applies to $w$.
     42 
     43 Output
     44 
     45 For each test case, output a single integer — the maximum spectacle of a suitable arrangement.
     46 
     47 Example
     48 
     49 Input
     50 
     51 ```
     52 5
     53 
     54 3 4 2
     55 
     56 9
     57 
     58 1 1 1 1 1 1 1 1 1
     59 
     60 2 1 1
     61 
     62 2
     63 
     64 5 7
     65 
     66 20 15 7
     67 
     68 9
     69 
     70 4 1 4 5 6 1 1000000000 898 777
     71 
     72 1984 1 1
     73 
     74 4
     75 
     76 5 4 1499 2004
     77 
     78 9 5 5
     79 
     80 6
     81 
     82 6 7 14 16 16 6
     83 ```
     84 
     85 Output
     86 
     87 ```
     88 21
     89 12
     90 49000083104
     91 3512
     92 319
     93 ```
     94 
     95 Note
     96 
     97 In the first test case of the first input set, the spectacle of the following sub-squares is summed:
     98 
     99  ![](https://espresso.codeforces.com/2b5720d298ae459a1a0537c1a313e1d97a00f238.png) Yellow color corresponds to the sub-squares, green — to the rest of the grid squares. 
    100 
    101 The picture shows the optimal arrangement of the gorillas. The spectacle of the arrangement is $4 + 4 + 3 + 3 + 4 + 3 = 21$.