Submission

Score: 0

User: NovemNotes

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

Language: cpp

Time: 0.002 second

Submitted On: 2025-11-03 08:13:43

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

#define int long long

const int N = 1e3+9;

int n,m;
int path[N][N];
int dp[N][N];

void show(){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cout << dp[i][j] << " ";
        }cout << "\n";
    }
    cout << "----------------\n";
}

int32_t main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    cin >> n >> m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin >> path[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(i==1&&j==1)dp[i][j]=path[i][j];
            else if(i==1)dp[i][j]=dp[i][j-1]+path[i][j];
            else if(j==1)dp[i][j]=dp[i-1][j]+path[i][j];
            else dp[i][j] = max(dp[i-1][j],dp[i][j-1])+path[i][j];
        }
    }
    // show();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(i==1&&j==1)continue;
            else if(i==1)dp[i][j]=min(dp[i][j],dp[i][j-1]);
            else if(j==1)dp[i][j]=min(dp[i][j],dp[i-1][j]);
            else{
                dp[i][j]=min(dp[i][j],max(dp[i-1][j],dp[i][j-1]));
            }
        }
    }
    // show();
    cout << (dp[n][m]>0? 0 : abs(dp[n][m])+1) << "\n";
    return 0;
}