Submission

Score: 100

User: Nay-O

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

Language: cpp

Time: 0.224 second

Submitted On: 2026-01-03 11:57:49

#include<bits/stdc++.h>
using namespace std;

int arr[1005][1005];

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	
	int n, m; cin >> n >> m;
	for(int i = 1; i <= n; i++){
		for(int  j = 1; j <= m; j++){
			cin >> arr[i][j];
		}
	}
	
	int l = 1, r = 1e9;
	
	while(l<r){
		int mid = (l+r)/2;
		vector<vector<int>> dp(n+5, vector<int>(m+5, 0));
		dp[1][1] = mid+arr[1][1];
		if(dp[1][1] <= 0){
			l = mid+1;
			continue;
		}
		for(int j = 2; j <= m; j++){
			dp[1][j] = dp[1][j-1];
			if(dp[1][j]>0){
				dp[1][j] += arr[1][j];
			}
		}
		for(int i = 2; i <= n; i++){
			for(int j = 1; j <= m; j++){
				dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
				if(dp[i][j]>0){
					dp[i][j] += arr[i][j];
				}
			}
		}
		if(dp[n][m] > 0){
			r = mid;
		}
		else{
			l = mid+1;
		}
//		cout << l << " " << r << "\n";
//		for(int i = 1; i <= n; i++){
//			for(int j = 1; j <= m; j++){
//				cout << dp[i][j] << " ";
//			} cout << "\n";
//		}cout << "\n\n";
	}
	
	cout << l;
	
	return 0;
}