二分+前缀和65pts求调(玄关)
查看原帖
二分+前缀和65pts求调(玄关)
1424067
C_0_a4S楼主2025/1/31 19:00

rt

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define max(x,y) (((x)>(y))?(x):(y))
void debug(int u){
	cerr<<u<<"IAKIOI\n";
}
inline int read(){
	int x=0,f=0;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')	f=1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return f?-x:x;
}
const int N=1e5+7;
int a[N];
int m[N];
int f[N];
signed main(){
	int n,x,sum=0;
	n=read(),x=read();
	
	
	for(int i=1;i<=n;i++){
		a[i]=read();
		m[i]=x-a[i];
		f[i]=f[i-1]+m[i];
	}
	
	for(int i=1;i<=n;i++)	sum+=a[i];
	
	if(x==0){
		printf("%lld",sum);
		return 0;
	}
//	debug(1);/
	int upd=0;
	for(int i=1;i<=n;i++){
		int l=i,r=n;
		int res=f[r]-f[l-1];
		while(l<=r){
			int mid=l+r>>1;
			if(f[mid]-f[l-1]>res){
				res=f[mid]-f[l-1];
				r=mid;
			}
			else if(f[r]-f[mid]>res){
				res=f[r]-f[mid];
				l=mid+1;
			}
			else{
				r=mid-1;
			}
		}
		upd=max(upd,res);
	}
	sum+=upd;
	printf("%lld",sum);
	return 0;
}
2025/1/31 19:00
加载中...