首页 > 考试 > 其他 >

Educational Codeforces Round 44 (Rated for Div. 2)

2018-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 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.

ExamplesInputCopy
4 2 1
2 2 1 2 3 2 2 3
OutputCopy
7
InputCopy
2 1 0
10 10
OutputCopy
20
InputCopy
1 2 1
5 2
OutputCopy
2
InputCopy
3 2 1
1 2 3 4 5 6
OutputCopy
0

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]
相关文章
最新文章
热点推荐