95pts wa on #1 求调
查看原帖
95pts wa on #1 求调
371409
Dangerise楼主2024/8/3 19:09
#include<bits/stdc++.h>
using namespace std;

#define int long long

inline int qread() {
	int ans=0;
	char c=getchar();
	bool f=0;
	while(c<'0'||c>'9') {
		if(c=='-') {
			f=1;
		}
		c=getchar();
	}
	while(c>='0'&&c<='9') {
		ans=ans*10+c-'0';
		c=getchar();
	}
	if(f) {
		return -ans;
	} else {
		return ans;
	}
}

const int N=2e5+1145;
const int INF=INT_MAX;

int n,m;
int t[N],w[N];

//对于花i,使l为相邻的左边的花,r为相邻的右边的花,统计花i仅有1朵花开放的时刻
inline int d(int l,int i,int r) {
	if(i<=0||i>n){
		return 0;
	}
	l=l<0?0:l;
	r=r>n+1?n+1:r;
	int a=0,b=0;
	if(t[i]<t[l]+m) {
		a=t[l]+m-t[i];
	}
	if(t[r]<t[i]+m) {
		b=t[i]+m-t[r];
	}
	int ans=m-a-b;
	return ans<0?0:ans;
}

int ds[N];
signed main() {
	n=qread(),m=qread();
	for(int i=1; i<=n; i++) {
		t[i]=qread();
	}

	sort(t+1,t+1+n);

	t[0]=-INF,t[n+1]=INF;

	int sum=0;
	for(int i=1; i<=n; i++) {
		ds[i]=d(i-1,i,i+1);
		sum+=ds[i];
	}

	int ans=0;
	for(int i=1; i<=n; i++) {
		int a1=ds[i-1],b1=ds[i+1];
		int a2=d(i-2,i-1,i+1);
		int b2=d(i-1,i+1,i+2);
		w[i]=a2-a1+b2-b1-ds[i]; 
     //如果移除花i,那么两边的花能够产生多少仅有一朵花开放的时刻
		ans=max(ans,w[i]);
	}

	printf("%lld\n",sum+m+ans);
	return 0;
}
2024/8/3 19:09
加载中...