常数，玄学

这是 AC 代码：

#include<bits/stdc++.h>
#define ll long long
#define mxn 5003
#define md 1000000007
#define pb push_back
#define mkp make_pair
#define ld long double
#define umap unordered_map
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define rept(i,a,b) for(int i=a;i<b;++i)
#define drep(i,a,b) for(int i=a;i>=b;--i)
#define pq priority_queue
using namespace std;
int n,k,a[mxn],sm,mx,ans;
inline bool check(int x,int mid){
	int sm=max(a[1],0);
	rep(i,2,n){
		if(sm+k>mid||sm+k+a[i]>mid){
			--x;
			sm=max(a[i],0);
		}else if(a[i]<0)sm=0;
		else sm+=k+a[i];
	}
	if(x<0)return 0;
	return 1;
}
signed main(){
	freopen("max.in","r",stdin);
	freopen("max.out","w",stdout);
	scanf("%d%d",&n,&k);
	rep(i,1,n)scanf("%d",&a[i]),mx=max(mx,a[i]);
	rept(i,2,n)sm+=a[i];
	if(a[1]>0)sm+=a[1];
	if(n>1&&a[n]>0)sm+=a[n];
	sm+=(n-1)*k;
	int ls=1e9;
	rept(i,0,n){
		int l=mx,r=ls;
		while(l<r){
			int mid=(l+r)>>1;
			if(check(i,mid))r=mid;
			else l=mid+1;
		}
		ans=max(ans,sm-(k+1)*i-l);
		ls=l;
	}
	cout<<ans;
	return 0;
}

这是 TLE 代码：

#include<bits/stdc++.h>
#define ll long long
#define mxn 5003
#define md 1000000007
#define pb push_back
#define mkp make_pair
#define ld long double
#define umap unordered_map
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define rept(i,a,b) for(int i=a;i<b;++i)
#define drep(i,a,b) for(int i=a;i>=b;--i)
#define pq priority_queue
using namespace std;
int n,k,a[mxn],sm,mx,ans;
inline bool check(int x,int mid){
	int sm=max(a[1],0);
	rep(i,2,n){
		if(sm+k>mid||sm+k+a[i]>mid){
			--x;
			sm=max(a[i],0);
		}else if(a[i]<0)sm=0;
		else sm+=k+a[i];
	}
	if(x<0)return 0;
	return 1;
}
signed main(){
	freopen("max.in","r",stdin);
	freopen("max.out","w",stdout);
	scanf("%d%d",&n,&k);
	rep(i,1,n)scanf("%d",&a[i]),mx=max(mx,a[i]);
	rept(i,2,n)sm+=a[i];
	sm+=(n-1)*k;
	if(a[1]>0)sm+=a[1];
	if(n>1&&a[n]>0)sm+=a[n];
	int ls=1e9;
	rept(i,0,n){
		int l=mx,r=ls;
		while(l<r){
			int mid=(l+r)>>1;
			if(check(i,mid))r=mid;
			else l=mid+1;
		}
		ans=max(ans,sm-(k+1)*i-l);
		ls=l;
	}
	cout<<ans;
	return 0;
}

两者的差距只有 sm+=(n-1)*k; 这行代码的位置不同。

时限 1000ms，\(n\le 5000,k\le 10^5\)。