在这里你可以轻松地获得一个AC数

#include <bits/stdc++.h>
//...
//真的对吗?
using namespace std;
int n,m,s,k; 
int a[1023][1023];
int e[1023][1023],dp[1023][1023];//进入时在结算后最多还剩多少钱，将要退出时最多还剩多少钱 
constexpr int inf=0x3f3f3f3f;
int p[1023],q[1023];//去的时候至少要多少钱和回来的时候最多还剩多少钱 
//p是说在结算这个格子之前至少要有多少钱 
bool flag1[1023],flag2[1023],flag[1023];//从可以开始的点出发，有哪些点是可以到达的 
int mian()
{
	cin>>n>>m>>s>>k;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cin>>a[i][j];
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			e[i][j]=dp[i][j]=-inf;
	for(int i=0;i<=m+1;i++)
		p[i]=inf,q[i]=-inf;
	p[0]=0,p[m+1]=0;
	for(int i=1;i<=m;i++)
	{
		int p=k<s+a[1][i]?k:s+a[1][i];
		if(p>=0)
			e[1][i]=p;
	}
	for(int i=1;i<n;i++)
	{
		for(int j=1;j<=m;j++)
			dp[i][j]=e[i][j];
		memset(flag1,0,sizeof(flag1));
		memset(flag2,0,sizeof(flag2));
		for(int j=m;j>=1;j--)
		{
			if(e[i][j]>=0)
			{
				int cur=j,remain=e[i][j];
				while(cur<=n&&remain>=0)
				{
					flag1[cur]=true;
					if(cur!=j)
						remain=min(remain+a[i][cur],k);
					cur++;
				}
			}
		}
		for(int j=1;j<=m;j++)
		{
			if(e[i][j]>=0)
			{
				int cur=j,remain=e[i][j];
				while(cur>=1&&remain>=0)
				{
					flag2[cur]=true;
					if(cur!=j)
						remain=min(remain+a[i][cur],k);
					cur--;
				}
			}
		}
		for(int j=1;j<=m;j++)
			flag[j]=flag1[j]|flag2[j];
		//考虑向左走找到刷钱点
		int last=-inf;
		for(int j=1;j<=m;j++)
			p[j]=inf,q[j]=-inf;
		for(int j=1;j<=m;j++)
		{
			//判断这是不是刷钱点
			//刷钱点是两个正数或者一正另一个<=0，应该算从最近的正数出发或者到最近的正数
			//我们认为刷钱点在j，当且仅当a_{j-1}与a_j构成了一个刷钱点，且a_j>0
			//其实a_j在左边也可以 
			//而且还要可以走到 
			if(flag[j]&&((j!=1&&a[i][j-1]+a[i][j]>0&&a[i][j]>=0)||(j!=m&&a[i][j]+a[i][j+1]>0&&a[i][j]>=0)))
			{
				//发现刷钱点
				p[j]=0,q[j]=k;
				last=j;
				continue; 
			}
			if(last==-inf)
				continue;
			//我们需要维护从上一个刷钱点到j还剩多少钱
			//还有从j走入上一个刷钱点在开始时至少要多少钱
			//第一点显然
			q[j]=min(q[j-1]+a[i][j],k);
			if(q[j]<0)//无法抵达j 
				q[j]=-inf;
			p[j]=max(p[j-1]-a[i][j],0);
			if(p[j]>k)
				p[j]=k;
		}
		for(int j=1;j<=m;j++)
			if(p[j-1]<=e[i][j])
				dp[i][j]=max(dp[i][j],q[j]);
		//向右走到刷钱点同理 
		last=inf;
		for(int j=1;j<=m;j++)
			p[j]=inf,q[j]=-inf;
		for(int j=m;j>=1;j--)
		{
			if(flag[j]&&((j!=m&&a[i][j+1]+a[i][j]>0&&a[i][j]>=0)||(j!=1&&a[i][j]+a[i][j-1]>0&&a[i][j]>=0)))
			{
				p[j]=0,q[j]=k;
				last=j;
				continue;
			}
			if(last==inf)
				continue;
			q[j]=min(q[j+1]+a[i][j],k);
			if(q[j]<0)
				q[j]=-inf;
			p[j]=max(p[j+1]-a[i][j],0);
			if(p[j]>k)
				p[j]=k;
		}
		for(int j=1;j<=m;j++)
			if(p[j+1]<=e[i][j])
				dp[i][j]=max(dp[i][j],q[j]);
		//但是我们可以从一个格子走到其他地方，需要考虑走到其他地方还剩多少
		//对于每两个刷钱点之间的格子，一定从刷钱点出发最优
		int remain=-inf;
		for(int j=1;j<=m;j++)//往右走 
		{
			if((remain>=0||flag[j])&&((j!=1&&a[i][j-1]+a[i][j]>0&&a[i][j]>=0)||(j!=m&&a[i][j]+a[i][j+1]>0&&a[i][j]>=0)))
			{
				remain=k;
				dp[i][j]=max(dp[i][j],remain);
				continue;
			}
			remain=min(remain+a[i][j],k);
			remain=max(dp[i][j],remain);
			if(remain<0)
				remain=-inf;
			dp[i][j]=max(dp[i][j],remain);
		}
		remain=-inf;
		for(int j=m;j>=1;j--)//往右走 
		{
			if((remain>=0||flag[j])&&((j!=1&&a[i][j-1]+a[i][j]>0&&a[i][j]>=0)||(j!=m&&a[i][j]+a[i][j+1]>0&&a[i][j]>=0)))
			{
				remain=k;
				dp[i][j]=max(dp[i][j],remain);
				continue; 
			}
			remain=min(remain+a[i][j],k);
			remain=max(dp[i][j],remain);
			if(remain<0)
				remain=-inf;
			dp[i][j]=max(dp[i][j],remain);
		}
		for(int j=1;j<=m;j++)
		{
			int next=min(k,dp[i][j]+a[i+1][j]);
			if(next>=0)
				e[i+1][j]=next;
		}
	}
	int ans=-inf;
	for(int i=1;i<=m;i++)
		if(e[n][i]>ans)
			ans=e[n][i];
	if(ans==-inf)
		cout<<"-1\n";
	else
		cout<<ans<<"\n";
	return 0;//完结撒花 
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int ID,t;
	cin>>ID>>t; 
	for(int i=1;i<=t;i++)
		mian();
	return 0;
}