记录编号	410616	评测结果	AAAAAAA
题目名称	209.工作分配	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.062 s
提交时间	2017-06-01 13:55:50	内存使用	15.55 MiB

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1e6+10;
typedef long double db;
typedef long long ll;
int n,k,C,b[N],q[N],head,tail;
ll dp[N];
db K(int i,int j){
	if (b[i+1]==b[j+1]) return dp[i]>dp[j]?-1e17:1e17;
	return db(dp[i]-dp[j])/(b[i+1]-b[j+1])+b[i+1]+b[j+1];
}
ll sqr(int x){return (ll)x*x;}
ll cost(int i,int j){return dp[j]+sqr(b[i]-b[j+1])+C;}

int main()
{
	freopen("divide.in","r",stdin);
	freopen("divide.out","w",stdout);
	scanf("%d%d%d",&n,&k,&C);
	for (int i=1;i<=n;i++) scanf("%d",&b[i]);
	sort(b+1,b+n+1);
	for (int i=1;i<k;i++) dp[i]=1e17;
	head=1;tail=0;
	for (int i=k;i<=n;i++){
		for (;head<tail&&K(q[tail-1],q[tail])>K(q[tail],i-k);tail--);
		q[++tail]=i-k;
		for (;head<tail&&K(q[head],q[head+1])<b[i]*2;head++);
		dp[i]=cost(i,q[head]);
	}
	printf("%lld\n",dp[n]);
	return 0;
}