Submission

Score: 0

User: singtoppy

Problemset: อัศวินขี่ม้าขาว

Language: cpp

Time: 0.002 second

Submitted On: 2026-02-08 13:11:07

#include<bits/stdc++.h>

using namespace std;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n, m;
	cin >> n >> m;

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

	int l = 0, r = INT_MAX;
	vector<vector<int>> dp(n, vector<int>(m, INT_MIN));
	dp[n - 1][m - 1] = v[n - 1][m - 1] + 1;

	for(int i = n - 2; i >= 0; i--) {
		dp[i][m - 1] = dp[i + 1][m - 1] + v[i][m - 1];
	}

	for(int i = m - 2; i >= 0; i--) {
		dp[n - 1][i] = dp[n - 1][i + 1] + v[n - 1][i];
	}

	for(int i = n - 2; i >= 0; i--) {
		for(int j = m - 2; j >= 0; j--) {
			dp[i][j] = max(dp[i + 1][j], dp[i][j + 1]) + v[i][j];
		}
	}

	for(int i = n - 2; i >= 0; i--) {
		dp[i][m - 1] = min(dp[i][m - 1], dp[i + 1][m - 1]);
	}

	for(int i = m - 2; i >= 0; i--) {
		dp[n - 1][i] = min(dp[n - 1][i], dp[n - 1][i + 1]);
	}

	for(int i = n - 2; i >= 0; i--) {
		for(int j = m - 2; j >= 0; j--) {
			dp[i][j] = max(dp[i + 1][j], dp[i][j + 1]) + dp[i][j];
		}
	}

	// for(int i = 0; i < n; i++) {
	// 	for(int j = 0; j < m; j++) {
	// 		cout << dp[i][j] << ' ';
	// 	}

	// 	cout << '\n';
	// }

	int res = dp[0][0];

	if(res > 0) {
		cout << 0;
	}
	else {
		cout << abs(res) + 1;
	}

	return 0;
}