1695C - Zero Path - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define ld long double
#define S string
#define MP map<int,int>
#define UMP unordered_map<int,int>
#define PR pair<int,int>
#define V vector<int>
#define ST set<int>
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define loop(n) for (int i = 0; i < (n); i++)
#define loop1(n) for (int i = 1; i < (n); i++)
#define Yes cout << "YES" << endl
#define No cout << "NO" << endl
#define P(x) cout << (x) << endl
#define PS(x) cout << (x) <<" "
#define MaxHeap priority_queue <int>
#define MinHeap priority_queue <int, vector<int>, greater<int>>
#define Mod 998244353
#define R return

int gcd(int a, int b) {
	if (b == 0) return a;
	return gcd(b , a % b);
}

int lcm(int a, int b) {
	return ((a * b) / gcd(a, b));
}

vector<bool> isPrime(int n) {
	vector<bool> vec(n + 1, true);
	vec[0] = false; vec[1] = false;

	for (int i = 2; i * i <= n ; i++) {
		for (int j = 2 * i; j <= n and vec[i] == true; j += i) {
			vec[j] = false;
		}
	}
	return vec;
}

int power(int x, int y) {
	if (y == 0) {
		return 1;
	}
	int p = power(x, y / 2);
	if (y % 2 == 0) {
		return (p % Mod * p) % Mod;
	}
	else {
		return (x * p % Mod * p) % Mod;
	}
}

int modulo_inverse(int n) {
	return power(n, Mod - 2);
}

int factorial(int n) {
	vector<int> fact(n + 1);
	fact[0] = 1;
	for (int i = 1; i < n + 1; i++) {
		fact[i] = (fact[i - 1] * i) % Mod;
	}
	return fact[n];
}

int nCr(int n, int r) {
	if (r == 0 or n == 0) return 1;
	int fac[n + 1];
	fac[0] = 1;
	for (int i = 1; i < n + 1; i++)
		fac[i] = (fac[i - 1] * i) % Mod;
	return (fac[n] % Mod * modulo_inverse(fac[r]) % Mod * modulo_inverse(fac[n - r]) % Mod) % Mod;
}

void solve() {
	int n, m;
	cin >> n >> m;

	vector<vector<int>> grid(n, vector<int> (m));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> grid[i][j];
		}
	}

	if ((n + m - 1) % 2 == 1) {
		cout << "NO" << endl;
		return;
	}

	vector<vector<pair<int, int>>> dp(n, vector<pair<int, int>> (m, {INT_MAX, INT_MIN}));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (i == 0 and j == 0) {
				dp[i][j].second = grid[i][j];
				dp[i][j].first = grid[i][j];
			} else if (i == 0) {
				dp[i][j].second = grid[i][j] + dp[i][j - 1].second;
				dp[i][j].first = grid[i][j] + dp[i][j - 1].first;
			} else if (j == 0) {
				dp[i][j].second = grid[i][j] + dp[i - 1][j].second;
				dp[i][j].first = grid[i][j] + dp[i - 1][j].first;
			} else {
				dp[i][j].second = max(dp[i - 1][j].second , dp[i][j - 1].second) + grid[i][j];
				dp[i][j].first = min(dp[i - 1][j].first , dp[i][j - 1].first) + grid[i][j];
			}
			//cout << dp[i][j].first << " " << dp[i][j].second << " ";
		}
		//cout << endl;
	}

	if (dp[n - 1][m - 1].first <= 0 and dp[n - 1][m - 1].second >= 0) {
		cout << "YES" << endl;
	} else {
		cout << "NO" << endl;
	}
}

signed main() {

#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif

	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int t = 1;
	cin >> t;

	while (t--) {
		solve();
	}

	return 0;
}