1695C-Zero_Path.cpp

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  int t; cin>>t;
  while(t--){
    int n,m; cin>>n>>m;
    int g[n][m];
    for(int i=0;i<n;++i) for(int j=0;j<m;++j){
      cin>>g[i][j];
    }
    if((n+m-1) % 2 == 1){
      cout<<"NO\n";
      continue;
    }
    int mn[m],mx[m];
    memset(mn,0x3f,sizeof mn);
    memset(mx,-0x3f,sizeof mx);
    for(int i=0;i<n;++i) for(int j=0;j<m;++j){
      if(!i && !j) mn[j]=mx[j]=g[i][j];
      else if(!j) mn[j]+=g[i][j],mx[j]+=g[i][j];
      else mn[j]=min(mn[j],mn[j-1])+g[i][j],
        mx[j]=max(mx[j],mx[j-1])+g[i][j];
    }
    cout<<(mn[m-1]<=0 && 0<=mx[m-1] ? "YES\n":"NO\n");
  }
  return 0;
}