15pts 求条

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e3+10,INF=LLONG_MAX;
inline int read(){
    int x=0,f=1;char c=getchar();
    while(!isdigit(c))f=c=='-'?-f:f,c=getchar();
	while(isdigit(c))x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x*f;
}
int n,m,a[N],tot,MAXN=-INF;
struct node{
	int a,l,r;
}b[N];
signed main()
{
	n=read(),m=read();
	for(int i=1;i<=n;i++)a[i]=read(),MAXN=max(MAXN,a[i]);
	for(int i=1;i<=m;i++){
		tot=0;
		int sum=0,l=1,r=0,MINN=INF;
		for(int j=1;j<=n;j++)MINN=min(MINN,a[j]);
		bool flag=0;
		for(int j=1;j<=n;j++){
			if(a[j]==MINN)flag=1;
			if(a[j]!=MAXN)sum++,r++;
			else{
				if(sum>0&&flag)b[++tot]={sum,l,r};
				sum=0,l=j+1,r=j,flag=0;
			}
		}
		if(sum>0&&flag)b[++tot]={sum,l,r};
		if(!tot){
			puts("0");
			return 0;
		}flag=0;
		int L1=b[1].l,R1=b[1].r,L2=b[tot].l,R2=b[tot].r;
		if(b[1].l==1&&b[tot].r==n)b[1].a+=b[tot].a,tot--,flag=1;
		int maxn=-1;
		int v=-1;
		for(int j=1;j<=tot;j++)if(b[j].a>maxn)maxn=b[j].a,v=j;
		if(flag&&v==1){
			for(int j=L1;j<=R1;j++)a[j]++;
			for(int j=L2;j<=R2;j++)a[j]++;
		}
		else for(int j=b[v].l;j<=b[v].r;j++)a[j]++;
	} 
	int minn=INF;
	int maxn=-INF;
	for(int i=1;i<=n;i++)maxn=max(maxn,a[i]),minn=min(minn,a[i]);
	cout<<maxn-minn<<endl;
    return 0;
}