Submission

Score: 0

User: hmmm

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

Language: cpp

Time: 0.002 second

Submitted On: 2026-02-08 20:59:19

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

int main(){
    int n,m;
    cin>>n>>m;
    vector<vector<long long>> vec(n+2,vector<long long> (m+2));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>vec[i][j];
        }
    }    
    long long l = 0 , r = 1e12;
	while(l < r){
	    long long mid = l + (r - l) / 2;
	    vector<vector<long long>> dp(n+2, vector<long long>(m+2, -1e18));
	
	    dp[1][1] = vec[1][1] + mid;
	    if(dp[1][1] <= 0){
	        l = mid + 1;
	        continue;
	    }
	
	    for(int i=1;i<=n;i++){
	        for(int j=1;j<=m;j++){
	            if(i==1 && j==1) continue;
	
	            long long best = max(dp[i-1][j], dp[i][j-1]);
	            if(best > 0){
	                dp[i][j] = best + vec[i][j];
	                if(dp[i][j] <= 0) dp[i][j] = -1e18;
	            }
	        }
	    }
	
	    if(dp[n][m] > 0) r = mid;
	    else l = mid + 1;
	}
	cout << l;
}