Submission

Score: 100

User: sorrkub

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

Language: cpp

Time: 0.440 second

Submitted On: 2026-02-08 21:26:02

#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 = 1 , r = 1e18;
    while(l<r){
        vector<vector<long long>> dp(n+2,vector<long long> (m+2 ,-1e18));
        dp[0][1] = 0;
        long long mid = l + (r-l)/2;
        //cout<<mid<<"\n";
        vec[1][1] +=mid;
        if(vec[1][1] < 0 ){
            l = mid + 1;
            vec[1][1] -=mid;
            continue;
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                dp[i][j] = max(dp[i][j-1],dp[i-1][j])+vec[i][j];
                if(dp[i][j] <=0){
                    dp[i][j] = -1e18;
                }
            }
        }
        if(dp[n][m] >0 ){
            r = mid;
        }
        else{
            l = mid+1;
        }
        vec[1][1] -= mid;
        // for(int i = 1;i<=n;i++){
        //     for(int j=1;j<=m;j++){
        //         cout<<dp[i][j]<<" ";
        //     }
        //     cout<<"\n";
        // }
        // cout<<"\n";
    } 
    cout<<l;
}