记录编号	597079	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	HS 的 Eula	最终得分	100
用户昵称	flyfree	是否通过	通过
代码语言	C++	运行时间	1.363 s
提交时间	2024-11-21 18:00:12	内存使用	7.27 MiB

#include<bits/stdc++.h>
using namespace std;
#define ll long long
inline ll read(){
	ll x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}
ll dp[510][510][2],pre[510];
ll n,m,beg,ans;
int main(){
	freopen("Eulalover.in","r",stdin);
	freopen("Eulalover.out","w",stdout);
	n=read(),m=read();
	for(int i=1;i<=n;i++){
		pre[i]=read();
	}
	pre[++n]=0;
	sort(pre+1,pre+1+n);
	for(int i=1;i<=n;i++)if(pre[i]==0)beg=i;
//	for(int i=1;i<=n;i++)cout<<pre[i]<<" ";
//	cout<<endl;
	for(int i=1;i<=n;i++)if(i!=beg)ans=max(ans,m-abs(pre[i]));
	for(int len=1;len<=n;len++){
		memset(dp,0,sizeof(dp));
//		dp[beg][beg][0]=dp[beg][beg][1]=
		for(int i=1;i<=n;i++)dp[i][i][0]=dp[i][i][1]=-1e18;
		dp[beg][beg][1]=dp[beg][beg][0]=0;
		for(int l=2;l<=len;l++){
			for(int i=1;i+l-1<=n;i++){
				ll j=i+l-1;
				if(beg<i||beg>j)continue;
				dp[i][j][1]=max(dp[i][j-1][1]+m-(len-l+1)*(pre[j]-pre[j-1]),dp[i][j-1][0]+m-(len-l+1)*(pre[j]-pre[i]));
				dp[i][j][0]=max(dp[i+1][j][0]+m-(len-l+1)*(pre[i+1]-pre[i]),dp[i+1][j][1]+m-(len-l+1)*(pre[j]-pre[i]));
//				cout<<i<<" "<<j<<" "<<dp[i][j][0]<<" "<<dp[i][j][1]<<endl;
				ans=max(ans,max(dp[i][j][0],dp[i][j][1]));
			}
		}
	}
	cout<<ans;
	return 0;
}