Submission

Score: 0

User: hmmm

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

Language: cpp

Time: 0.002 second

Submitted On: 2026-02-08 20:54:18

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