Submission

[PPPPPPPPPPPPPPP]

Score: 100

User: Nakornrat

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

Language: cpp

Time: 0.200 second

Submitted On: 2025-03-22 23:55:47

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
int n, m;
const int inf = -1e9;
vector<vector<int>> gh;
bool valid(int hp){
    vector<vector<int>> dp(n, vector<int>(m, inf));
    dp[0][0] = gh[0][0]+hp;
    if(dp[0][0]<=0)return false;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(i==0&&j==0)continue;
            int mx = inf;
            if(i>0&&dp[i-1][j]>0)mx = max(mx, gh[i][j]+dp[i-1][j]);
            if(j>0&&dp[i][j-1]>0)mx = max(mx, gh[i][j]+dp[i][j-1]);
            dp[i][j] = mx;
        }
    }
    return dp[n-1][m-1]>0;
}
int main()
{
    ios::sync_with_stdio(false);cin.tie(0);
    cin>>n>>m;
   gh.assign(n, vector<int>(m));
   for(int i=0;i<n;i++){
    for(int j=0;j<m;j++)cin>>gh[i][j];
   }
   int l = 1, r = INT_MAX;
   while(l<r){
    int mid = l+(r-l)/2;
    if(valid(mid)){
        r = mid;
    }else{
        l = mid + 1;
    }
   }
   cout<<l<<endl;
}