Codeforces Round 890 (Div. 2) supported by Constructor Institute ————C - To Become Max

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=1e6+7; 
int mod=1e9+7;
int a[N];
int n,k;
void solve()
{
	cin>>n>>k;
	int x;
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		ans=max(ans,a[i]);
	}
	a[n+1]=a[n]-1; //这里多加个，让最后两位也计算
	n++;
	for(int i=2;i<n;i++)
	{
		int x=a[i],xx=a[i+1]+1; //起点的下上限 
		xx=max(xx,x); //注意这里要保证xx>=x
		int w=a[i]; //表示上一位的值
		int sss=a[i]; //j+1 位置的值
		int p=0;  //j+1位置达到sss所花费的值
		for(int j=i-1;j>=1;j--) //二层循环，每次只看当前位置
		{
			w=max(w+1,a[j]+1);//当前位置的最大值
			if(w-(i-j)<=xx) //如果最值大于上限，break
			{
				int cc=p+w-a[j]+(i-j)*(w-1-sss); //当前位置达到最值的花费，
				sss=w; //记录当前位置，最值，方便下次用
				p=cc; //记录当前花费，方便下次累加
				if(cc<=k)//当前位置达到最值时，花费是否满足
				{
					ans=max(ans,w); //更新答案
					int kk=k-cc; 
					ans=max(ans,min(xx+i-j,w+kk/(i-j+1))); //剩余操作次数，对区间整体操作，注意小于上界
				}
				else break;
			}
			else break;
		}
	} 
	cout<<ans<<'\n';
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t=1;
	cin>>t; 
	while(t--)
	{
		solve();
	}
	return 0;
}