记录编号	7983	评测结果	AAAATTTTEA
题目名称	工作分配	最终得分	50
用户昵称	苏轼	是否通过	未通过
代码语言	Pascal	运行时间	4.568 s
提交时间	2008-11-12 16:51:18	内存使用	2.02 MiB

program cch(input,output);
const
 maxf=1000000000;
var
 i,j,k,c,n:longint;
 f:array[0..100000] of int64;
 data:array[1..100000] of longint;
 a:array[1..100000] of int64;

procedure qsort(l,r:longint);
var
 x,tmp,i,j:longint;
begin
 i:=l; j:=r;
 x:=a[(l+r) shr 1];
 repeat
  while a[i]<x do inc(i);
  while a[j]>x do dec(j);
  if i<=j then
   begin
    tmp:=a[i]; a[i]:=a[j]; a[j]:=tmp;
    inc(i); dec(j);
   end;
 until i>j;
 if i<r then qsort(i,r);
 if j>l then qsort(l,j);
end;

begin
 assign(input,'divide.in');
 assign(output,'divide.out');
 reset(input);
 rewrite(output);
 readln(n,k,c);
 for i:=1 to n do read(data[i]);
 for i:=1 to n do a[i]:=data[i];
 qsort(1,n);
 for i:=0 to k-1 do f[i]:=maxf;
 for i:=k to n do f[i]:=c+sqr(a[i]-a[1]);
 for i:=1 to n do
  for j:=k to i-k do
   if f[i]>f[j]+sqr(a[i]-a[j+1])+c then
     f[i]:=f[j]+sqr(a[i]-a[j+1])+c;
 write(f[n]);
 close(input);
 close(output);
end.