记录编号	38807	评测结果	AAAAAAAAAA
题目名称	工作指派	最终得分	100
用户昵称	kaaala	是否通过	通过
代码语言	C++	运行时间	0.014 s
提交时间	2012-06-14 18:33:06	内存使用	0.43 MiB

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>

using namespace std;

const int oo=~0u>>2;

int N,K,C,A[10010];
long long f[10010];

int cmp(const void *a,const void *b)
{
	if(*(int*)a>*(int*)b)
		return 1;
	return -1;
}

void dp()
{
	int pre=0;
	for(int i=1;i<=N;i++)
		f[i]=oo;
	f[0]=0;
	for(int i=K;i<=N;i++)
	{
		int u=pre;
		for(int j=pre;j<=i-K;j++)
			if(f[i]>=f[j]+(A[i]-A[j+1])*(A[i]-A[j+1])+C)
			{
				f[i]=f[j]+(A[i]-A[j+1])*(A[i]-A[j+1])+C;
				u=j;
			}
		pre=u;
	}
}

int main()
{
	freopen("dividea.in","r",stdin);
	freopen("dividea.out","w",stdout);
	scanf("%d%d%d",&N,&K,&C);
	for(int i=1;i<=N;i++)
		scanf("%d",&A[i]);
	qsort(A+1,N,sizeof(A[0]),cmp);
	dp();
	printf("%lld\n",f[N]);
	return 0;
}