Submission

Score: 100

User: singtoppy

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

Language: cpp

Time: 0.080 second

Submitted On: 2026-02-08 13:22:15

#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 + 1, vector<int>(m + 1));
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			cin >> v[i][j];
		}
	}

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

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

	// 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[1][0];

	cout << res;

	return 0;
}