#include <bits/stdc++.h>
#define int long long

using namespace std;

int c,t;
int n,m,s,k;
int dp[1002],a[1002],ans;
bool b,vis[1002];//b为可否同行，如果b=0了则说明当前行不能到达，接下来的计算就没有意义了。vis表示这个位置是否能达到
//go表示向一个方向进行一次来回可以刷多少钱，cost有两个作用：1.表示进行一次来回的前提是有多少钱；2.刷钱的上限为k-cost[i]+a[i]（因为可能回来时会经过负数，导致达不到k）
//后缀l表示只考虑向左来回，r表示只考虑向右来回
int gol[1002],costl[1002];
int gor[1002],costr[1002];
bool sh[1002];//表示这个位置是否可以刷钱

bool check(int num);

signed main(){
    // freopen("journey7.in","r",stdin);
    scanf("%lld%lld",&c,&t);
    while(t--){
        b=1;
        scanf("%lld%lld%lld%lld",&n,&m,&s,&k);
        for(int i=1;i<=m;i++)   dp[i]=s,vis[i]=sh[i]=0;
        while(n--){
            for(int i=1;i<=m;i++){
                scanf("%lld",&a[i]);
                if(!vis[i] && dp[i]+a[i]>=0)    dp[i]=min(dp[i]+a[i],k);
                else    vis[i]=1,dp[i]=LLONG_MIN;
            }
            if(n==0)    break;
            if(!b)  continue;
            b=check(m);
            for(int i=2;i<=m;i++){
                gol[i]=max(0LL,gol[i-1])+a[i-1]+a[i];
                if(gol[i]>0)    sh[i]=1;
                costl[i]=max(0LL,costl[i-1]-a[i-1]);
                if(gol[i]<0)    costl[i]=0;
            }
            for(int i=m-1;i;i--){
                gor[i]=max(0LL,gor[i+1])+a[i+1]+a[i];
                if(gor[i]>0)    sh[i]=1;
                costr[i]=max(0LL,costr[i+1]-a[i+1]);
                if(gor[i]<0)    costr[i]=0;
            }
            for(int i=1;i<=2;i++){
                    for(int i=1;i<=m;i++){
                    if(!vis[i] && sh[i])  dp[i]=min(k,max({dp[i],dp[i]>=costl[i] && gol[i]>0?k-costl[i]+a[i]:0,dp[i]>=costr[i] && gor[i]>0?k-costr[i]+a[i]:0}));
                    if(dp[i]+a[i+1]>=0) vis[i+1]=0;
                    dp[i+1]=min(k,max(dp[i+1],dp[i]+a[i+1]));
                }
                for(int i=m;i;i--){
                    if(!vis[i] && sh[i])  dp[i]=min(k,max({dp[i],dp[i]>=costl[i] && gol[i]>0?k-costl[i]+a[i]:0,dp[i]>=costr[i] && gor[i]>0?k-costr[i]+a[i]:0}));
                    if(dp[i]+a[i-1]>=0) vis[i-1]=0;
                    dp[i-1]=min(k,max(dp[i-1],dp[i]+a[i-1]));
                }
            }
        }
        if(!b){
            printf("-1\n");
            continue;
        }
        ans=-1;
        for(int i=1;i<=m;i++)   if(!vis[i]) ans=max(ans,dp[i]);
        printf("%lld\n",ans);
    }
    return 0;
}

bool check(int num){
    for(int i=1;i<=num;i++) 
        if(!vis[i])
            return 1;
    return 0;
}

就是性质 B 的测试点过不了...给给 hack ，或帮帮调调。

$QAQ$