Educational Codeforces Round 44 (Rated for Div. 2)

18-06-29

Educational Codeforces Round 44 (Rated for Div 2) 。

C. Liebig's Barrelstime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

$\text{[math]}$

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.

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≤10⁵, 1≤n·k≤10⁵, 0≤l≤10⁹).

The second line contains m=n·k space-separated integers a₁,a₂,...,a_m (1≤a_i≤10⁹) — 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 |v_x-v_y|≤l for any 1≤x≤n and 1≤y≤n.

ExamplesInputCopy

4 2 1
2 2 1 2 3 2 2 3

OutputCopy

InputCopy

2 1 0
10 10

OutputCopy

InputCopy

1 2 1
5 2

OutputCopy

InputCopy

3 2 1
1 2 3 4 5 6

OutputCopy

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.

这道题忍住了看题解。自己独立思考了QAQ。但是div2的C题还是属于那种自己可以做但需要花很长时间的那种，希望慢慢进步（D题先凑合着题解自己写QAQ）补完了这道题去洗澡澡题意很简单，给n,k,l, l是体积限定的条件见上，k是每个小序列的长度，n是小序列的个数。再给你N*K个数这道题是一道贪心的题目，我的想法是对于这一系列数字来说：对于分成的k个序列，每个序列中最小的就是代表这个体积，在符合情况| Vi-Vj |<=l的情况下取尽可能大的体积。首先对数组排序，首先排序后的arr[1]肯定是一个序列的体积（放哪里都是最小的），那么我要满足l的限定条件的话，体积的取值一定在arr[1]~arr[1]+l中，找到arr[1]+l这个值所对应的数组下标。对于一般情况，n<>

再考虑涵盖不掉全部的情况，比如刚才的例子，对于刚刚的6来说，只剩下6和7了，自然涵盖完，但是如果n是3呢，就只能一个取6 一个取7，单独判断一下就好（k不行变成k-1一直减到0为止（保证k过后剩下的元素个数大于等于还没取得序列个数））说了一大堆，上代码（懒得加注释了改了好多遍才过之前一直WA7是用样例推得时候最小为1,就一直l+1到好久....）菜啊qwq

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long LL;
LL arr[100010];
LL tem[100010];


int main()
{
	LL sum=0;
	LL n,k;
	LL l;
	cin>>n>>k>>l;
	for(LL i=1;i<=n*k;i++)
	{
		cin>>arr[i];
	}
	sort(arr+1,arr+1+n*k);
	LL j=0;
	tem[++j]=1;
	int ans;
	for(LL i=1;i<=n*k;i++)
	{
		if(arr[i+1]!=arr[i])
		tem[++j]=i;
		else tem[j]=i;
		if(arr[i]==l+arr[1])
		ans=i;
		else if(arr[i]<>