Liebig's Barrels (Codeforces 985C)
Tags: Greedy, greedy

You have m = n·k wooden staves. The i-th stave has length ai. 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 vj 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. |vx - vy| ≤ l for any 1 ≤ x ≤ n and 1 ≤ y ≤ n.Print maximal total sum of volumes of equal enough barrels or 0 if it's impossible to satisfy the condition above.

Input: The first line contains three space-separated integers n, k and l (1 ≤ n, k ≤ 105, 1 ≤ n·k ≤ 105, 0 ≤ l ≤ 109).The second line contains m = n·k space-separated integers a1, a2, ..., am (1 ≤ ai ≤ 109) — lengths of staves.

Output: 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 |vx - vy| ≤ l for any 1 ≤ x ≤ n and 1 ≤ y ≤ n.

Note: 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.

Sample Inputs:
4 2 1
2 2 1 2 3 2 2 3

2 1 0
10 10

1 2 1
5 2

3 2 1
1 2 3 4 5 6

Sample Outputs:
7

20

2

0

Solution (Python):
R = lambda : map(int, input().split())
(n, k, l) = R()
a = sorted(R())
s = c = 0
for i in range(n * k - 1, -1, -1):
    c += 1
    if a[i] - a[0] <= l and c >= k:
        s += a[i]
        c -= k
print((s, 0)[c > 0])

Solution (Python):
(n, k, l) = map(int, input().split())
staves = sorted(list(map(int, input().split())))
sum = 0
big = -1
small = 0
for i in range(len(staves) - 1, -1, -1):
    if staves[i] - staves[0] <= l:
        big = i
        break
if big < n - 1:
    print(0)
else:
    small = big - (n - 1)
    i = 0
    while i < small:
        small += 1
        sum += staves[i]
        i += k
    for i in range(small, big + 1):
        sum += staves[i]
    print(sum)

Solution (Python):
from bisect import *
R = lambda : map(int, input().split())
(n, k, l) = R()
a = sorted(R())
t = bisect_right(a, a[0] + l)
if t < n:
    print(0)
else:
    s = sum(a[0:t:k])
    n -= (t - 1) // k + 1
    i = t - 1
    while n:
        if i % k:
            s += a[i]
            n -= 1
        i -= 1
    print(s)