CF985C Liebig's Barrels

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. Let volume $ v_{j} $ of barrel $ j $ be equal to the length of the minimal stave in it. 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}|

N/A

N/A

In the first example you can form the following barrels: $ [1,2] $ , $ [2,2] $ , $ [2,3] $ , $ [2,3] $ . In the second example you can form the following barrels: $ [10] $ , $ [10] $ . In the third example you can form the following barrels: $ [2,5] $ . 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.