记录编号	8088	评测结果	AAAATTTTTA
题目名称	工作分配	最终得分	50
用户昵称	zqzas	是否通过	未通过
代码语言	C++	运行时间	5.022 s
提交时间	2008-11-12 20:30:08	内存使用	15.52 MiB

#include <iostream>

#define MAXN 1000010
#define INF 0x7fffffffffffffffLL

using namespace std;

long long data[MAXN];
long long n,k,c,ans,f[MAXN];


void run()
{
	int i,p;
	long long min;
	f[0]=0;
	for (i=1;i<=n;i++)
	{
		min=INF;
		for (p=0;p<=i-k;p++)
		{
			if (f[p]<INF && f[p]+c+(data[i]-data[p+1])*(data[i]-data[p+1])<min)
				min=f[p]+c+(data[i]-data[p+1])*(data[i]-data[p+1]);
		}
		f[i]=min;
	}
	ans=f[n];
}

int cmp(const void *a,const void *b)
{
	return *(long long *)a - *(long long *)b;
}

void ini()
{
	int i;
	scanf("%lld%lld%lld",&n,&k,&c);
	for (i=1;i<=n;i++)
		scanf("%lld",&data[i]);
	qsort(data,n+1,sizeof(data[0]),cmp);
}

int main()
{
    freopen("divide.in","r",stdin);
    freopen("divide.out","w",stdout);
	ini();
	run();
	cout<<ans;
    return 0;
}