记录编号	38831	评测结果	AAAAAAAAAA
题目名称	工作指派	最终得分	100
用户昵称	ZhouHang	是否通过	通过
代码语言	C++	运行时间	0.124 s
提交时间	2012-06-15 09:11:26	内存使用	3.11 MiB

/*
ID: englanq1
PROG:
LANG: C++
*/
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<algorithm>
using namespace std;

int n,K,C;
long long f[1000005];
long long a[1000005];

void init()
{
     freopen("dividea.in","r",stdin);
     freopen("dividea.out","w",stdout);
}

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

void readdata()
{
     scanf("%d%d%d\n",&n,&K,&C);
     int i;
     for(i=1; i<=n; i++)
     scanf("%d",&a[i]);
     qsort(a+1,n,sizeof(a[1]),cmp);
}

void work()
{
     int i,j,last,noww;
     memset(f,0x7f,sizeof(f));
     f[0]=0;
     last=0;
     for(i=K; i<=n; i++)
     {
                 noww=last;
                 for(j=last; 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;
                      noww=j;                                                                                  
                 }
                 last=noww;
     }
}

void print()
{
     printf("%I64d\n",f[n]);
}

int main()
{
	
    init();
    readdata();
    work();
    print();
    return 0;
}