codeforces-scrape

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

985C.md (2229B)


      1 Source: https://codeforces.com/problemset/problem/985/C
      2 
      3 C. Liebig's Barrels
      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 have *m* = *n*·*k* wooden staves. The *i*-th stave has length *a**i*. You have to assemble *n* barrels consisting of *k* staves each, you can use any *k* staves to construct a barrel. Each stave must belong to exactly one barrel.
     22 
     23 Let volume *v**j* of barrel *j* be equal to the length of the minimal stave in it.
     24 
     25  ![](https://espresso.codeforces.com/1320351d3d4eb590d9aa6e2709b4098ace50af62.png) 
     26 
     27 You want to assemble exactly *n* barrels with the maximal total sum of volumes. But you have to make them equal enough, so a difference between volumes of any pair of the resulting barrels must not exceed *l*, i.e. |*v**x* - *v**y*| ≤ *l* for any 1 ≤ *x* ≤ *n* and 1 ≤ *y* ≤ *n*.
     28 
     29 Print maximal total sum of volumes of equal enough barrels or 0 if it's impossible to satisfy the condition above.
     30 
     31 Input
     32 
     33 The first line contains three space-separated integers *n*, *k* and *l* (1 ≤ *n*, *k* ≤ 105, 1 ≤ *n*·*k* ≤ 105, 0 ≤ *l* ≤ 109).
     34 
     35 The second line contains *m* = *n*·*k* space-separated integers *a*1, *a*2, ..., *a**m* (1 ≤ *a**i* ≤ 109) — lengths of staves.
     36 
     37 Output
     38 
     39 Print single integer — maximal total sum of the volumes of barrels or 0 if it's impossible to construct exactly *n* barrels satisfying the condition |*v**x* - *v**y*| ≤ *l* for any 1 ≤ *x* ≤ *n* and 1 ≤ *y* ≤ *n*.
     40 
     41 Examples
     42 
     43 Input
     44 
     45 ```
     46 4 2 1  
     47 2 2 1 2 3 2 2 3
     48 ```
     49 
     50 Output
     51 
     52 ```
     53 7
     54 ```
     55 
     56 Input
     57 
     58 ```
     59 2 1 0  
     60 10 10
     61 ```
     62 
     63 Output
     64 
     65 ```
     66 20
     67 ```
     68 
     69 Input
     70 
     71 ```
     72 1 2 1  
     73 5 2
     74 ```
     75 
     76 Output
     77 
     78 ```
     79 2
     80 ```
     81 
     82 Input
     83 
     84 ```
     85 3 2 1  
     86 1 2 3 4 5 6
     87 ```
     88 
     89 Output
     90 
     91 ```
     92 0
     93 ```
     94 
     95 Note
     96 
     97 In the first example you can form the following barrels: [1, 2], [2, 2], [2, 3], [2, 3].
     98 
     99 In the second example you can form the following barrels: [10], [10].
    100 
    101 In the third example you can form the following barrels: [2, 5].
    102 
    103 In the fourth example difference between volumes of barrels in any partition is at least 2 so it is impossible to make barrels equal enough.