题解

#include <bits/stdc++.h>
using namespace std;
# define rep(i,a,b) for(int i=(a); i<=(b); ++i)
# define drep(i,a,b) for(int i=(a); i>=(b); --i)
typedef long long llong;
inline int readint(){
	int a = 0, c = getchar(), f = 1;
	for(; !isdigit(c); c=getchar())
		if(c == '-') f = -f;
	for(; isdigit(c); c=getchar())
		a = (a<<3)+(a<<1)+(c^48);
	return a*f;
}
void writeint(unsigned x){
	if(x > 9) writeint(x/10);
	putchar(char((x%10)^48));
}
inline void getMin(llong &x,const llong &y){
	if(y < x) x = y;
}

const int MAXN = 500005;
const long long INFTY = LONG_LONG_MAX>>1;
long long dp[2][MAXN];
int a[MAXN];

int main(){
	int n = readint(), s = readint();
	for(int i=1,nxt; i!=n; ++i){
		nxt = readint();
		a[i] = nxt-s, s = nxt;
	}
	sort(a+1,a+n,less<int>()); s = 0;
	fill(dp[0]+1,dp[0]+(MAXN<<1),INFTY);
	for(int i=1,fr=0,p=0; i!=n; ++i,fr^=1){
		s += a[i]; 
		const int mov = i*a[i];
		fill(dp[i&1],dp[i&1]+p+mov+1,INFTY);
		llong gap = llong(n)*s*s;
		rep(j,0,p) getMin(dp[i&1][j+s],dp[fr][j]+gap);
		gap = llong(i)*n*a[i]*a[i];
		const int step = n*(a[i]<<1); 
		for(int j=0; j<=p; ++j,gap+=step)
			getMin(dp[i&1][j+mov],dp[fr][j]+gap);
		p += mov; 
	}
	llong ans = INFTY;
	const int id = (n&1)^1;
	rep(i,0,s*(n-1)) getMin(ans,dp[id][i]-llong(i)*i);
	cout<<ans<<'\n';
	return 0;
}