NO IMAGE

題目描述
眾所周知Kelukin是一名宇宙級土豪,他公司的生意自然是相當的好。
現在他手上有n份工作要完成,每一份工作有一個土豪指標Ak。由於這些工作數量太多,Kelukin又懶,所以他無法一個人完成,他需要僱用很多工人來幫忙。可是Kelukin十分小氣,經常剋扣工資,因此沒有多少人願意幫他。而願意幫他的那些工人各個都是奇葩,而且他們非常精明,按工作量收費,小於k份的工作量他們是不會去做的,而他們完成一次工作要額外收C元。一個工人最多做一次工作。
Kelukin表示那些工作之間有很多是類似的,完成了第一份第二份能很快掃完,因此他這麼規定一個工人的報酬:若工人所做的工作的土豪指標為(T1,T2,T3,T4……,Tm),則他的報酬為C (maxTi-minTi)^2,1<=i<=m,m>=k。
作為Kelukin的貼身祕書,你有義務告訴他為了完成這n份工作最少要花多少錢。當然,Kelukin非常的小氣,他是不會給你工資的。
輸入
第一行三個正整數n、k、C(1≤k≤n≤10^6,0≤C≤10^9),之間用一個空格隔開。
第二行為n個正整數,描述n份工作的土豪指標(0<Ak≤10^9),之間用一個空格隔開。
輸出
一行僅一個整數,表示Kelukin最少需要支付的工資(保證答案不大於10^17)。
樣例輸入
2 1 1
2 4
樣例輸出
2
提示
【樣例說明】

如果分給一個工人做,收費為 1 (4 – 2) ^2 = 5。

如果分給兩個工人作,收費為 1 1 = 2。
所以最小收費為2。
【資料範圍】
對於50%的測試資料中保證有N≤1000。
對於70%的測試資料中保證有N≤50000。
對於100%的測試資料中保證有N≤1000000。

斜率優化裸題。。。調了半天發現佇列指標初值不對。。。

var
f,q:array[0..1000111] of int64;
a:array[0..1000111] of double;
n,k,c,i,st,ed:longint;
flag:boolean;
procedure sort(l,r:longint);
var
i,j:longint;
t,m:double;
begin
i:=l;j:=r;m:=a[(i j) div 2];
repeat
while a[i]<m do inc(i);
while a[j]>m do dec(j);
if i<=j then
begin
t:=a[i];a[i]:=a[j];a[j]:=t;
inc(i);dec(j);
end;
until i>j;
if i<r then sort(i,r);
if j>l then sort(l,j);
end;
function judge1(i,j,k:longint):boolean;
begin
if f[j] sqr(a[j 1])-f[k]-sqr(a[k 1])<=2*a[i]*(a[j 1]-a[k 1]) then exit(true)
else exit(false);
end;
function judge2(i,j,k:longint):boolean;
var
x1,x2,y1,y2:double;
begin
if (f[i] sqr(a[i 1])-f[j]-sqr(a[j 1]))*(a[j 1]-a[k 1])<=(a[i 1]-a[j 1])*(f[j]-f[k] sqr(a[j 1])-sqr(a[k 1]))
then exit(true)
else exit(false);
end;
begin
readln(n,k,c);
for i:=1 to n do
read(a[i]);
for i:=1 to k-1 do
f[i]:=1000000000000000;
sort(1,n);
st:=1;
ed:=1;
for i:=k to n do
begin
while (st<ed)and(judge1(i,q[st 1],q[st])) do inc(st);
f[i]:=f[q[st]] trunc(sqr(a[i]-a[q[st] 1])) c;
while (st<ed)and(judge2(i-k 1,q[ed],q[ed-1])) do dec(ed);
ed:=ed 1;
q[ed]:=i-k 1;
end;
write(f[n]);
end.