Submission

Score: 0

User: singtoppy

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

Language: cpp

Time: 0.002 second

Submitted On: 2026-02-08 12:56:11

#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));

	while(l < r) {
		int mid = (l + r) / 2;

		dp[0][0] = v[0][0] + mid;

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

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

		// for(int i = 1; i < n; i++) {
		// 	dp[i][0] = min(dp[i][0], dp[i - 1][0]);
		// }

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

		// for(int i = 1; i < m; i++) {
		// 	dp[0][i] = min(dp[0][i], dp[0][i - 1]);
		// }

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

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

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

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

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

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

		int res = dp[n - 1][m - 1];

		// cout << res << '\n';

		if(res < 1) {
			l = mid + 1;
		}
		else {
			r = mid;
		}

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

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

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

	cout << r;

	return 0;
}