Submission

Score: 0

User: singtoppy

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

Language: cpp

Time: 0.002 second

Submitted On: 2026-01-23 23:40:46

#include<bits/stdc++.h>

using namespace std;

#define pii pair<int, int>

const int N = 24;
const int INF = 1e9;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	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];
		}
	}

	//min spike and current count

	vector<vector<pii>> dp(n, vector<pii>(m, {INT_MIN, INT_MIN}));
	dp[0][0].first = v[0][0];
	dp[0][0].second = v[0][0];

	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			if(i + 1 < n) 
				dp[i + 1][j].first = max(dp[i + 1][j].first, dp[i][j].first + v[i + 1][j]);
			if(j + 1 < m) 
				dp[i][j + 1].first = max(dp[i][j + 1].first, dp[i][j].first + v[i][j + 1]);
			if(i - 1 >= 0)
				dp[i][j].second = max(dp[i][j].second, min(dp[i - 1][j].second, dp[i][j].first));
			if(j - 1 >= 0)
				dp[i][j].second = max(dp[i][j].second, min(dp[i][j - 1].second, dp[i][j].first));  
		}
	}

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

	// cout << '\n';

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

	cout << abs(dp[n - 1][m - 1].second) + 1 << '\n';
}