记录编号	597077	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	HS 的 Eula	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	4.336 s
提交时间	2024-11-21 17:51:41	内存使用	19.03 MiB

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,ll>
#define fi first
#define in inline
#define se second
#define mp make_pair
#define pb push_back
const int N = 1010;

ll read(){
	ll x = 0,f = 1;char c = getchar();
	for(;c < '0' || c > '9';c = getchar())if(c == '-')f = -1;
	for(;c >= '0' && c <= '9';c = getchar())x = (x<<1) + (x<<3) + c-'0';
	return x * f;
}

ll n,m;
ll f[2][N][N];
ll x[N];

int main(){
	n = read(),m = read();
	ll ans = 0;
	for(int i = 1;i <= n;i++)x[i] = read();
	sort(x+1,x+1+n);
	for(int len = 1;len <= n;len++){
		memset(f,-0x3f,sizeof f);
		for(int i = 1;i <= n;i++)f[0][i][i] = f[1][i][i] = m - abs(x[i]) * len;
		for(int l = 2;l <= len;l++){
			for(int i = 1;i + l - 1 <= n;i++){
				int j = i + l - 1;
				f[0][i][j] = max(f[0][i+1][j] - (x[i+1] - x[i]) * (len - j + i),
				f[1][i+1][j] - (x[j] - x[i]) * (len - j + i)) + m;
				f[1][i][j] = max(f[0][i][j-1] - (x[j] - x[i]) * (len - j + i),
				f[1][i][j-1] - (x[j]- x[j-1]) * (len - j + i)) + m;
			}	
		}
		for(int i = 1;i + len - 1 <= n;i++)ans = max({ans,f[0][i][i + len - 1],f[1][i][i + len - 1]});
	}
	printf("%lld\n",ans);

	return 0;

}