Algorithm
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.
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.
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.
4 2 1
2 2 1 2 3 2 2 3
7
2 1 0
10 10
20
1 2 1
5 2
2
3 2 1
1 2 3 4 5 6
0
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.
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <bits/stdc++.h>
using namespace std;
int n, k, l, mn = 2e9, have, a[100001];
int main() {
cin >> n >> k >> l;
for(int i = 0; i < n * k; ++i) {
cin >> a[i];
mn = min(mn, a[i]);
}
sort(a, a + n * k);
for(int i = 0; i < n * k; ++i) {
if(a[i] - mn > l)
break;
have = i + 1;
}
if(have < n) {
puts("0");
return 0;
}
int rem = n * k - have, take = 0;
long long tot = 0;
for(int i = have - 1; take < n && i >= 0; --i) {
if(rem < k - 1) {
++rem;
continue;
}
rem -= k - 1;
tot += a[i];
++take;
}
cout << tot << endl;
return 0;
}Input
2 2 1 2 3 2 2 3
Output
Demonstration
Codeforces Solution-C. Liebig's Barrels-Solution in C, C++, Java, Python,Liebig's Barrels,Codeforces Solution