Submission

[PPPPPP-SSSSSSSS]

Score: 0

User: Jibhong

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

Language: cpp

Time: 0.034 second

Submitted On: 2025-03-30 23:21:15

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
int mem[1005][1005];
int n,m;
int main(){
    cin>>n>>m;
    for(int i=0;i<n;++i){
        for(int j=0;j<m;++j){
            cin>>mem[i][j];
        }
    }
//     int l=1,r=20000005;
    int l=1,r=2e9;
    while(l<r){
        int mid=(l+r)/2;
        queue<pair<int,pii>>q;
        q.push({mid,{0,0}});
        bool ok=1;
        while(!q.empty()){
            auto [hp,amongus]=q.front();
            auto [x,y]=amongus;
            q.pop();
            if(x==n-1 && y==m-1){
                ok=0;
                break;
            }
            if(hp+mem[x][y]<=0)continue;
            if(x<n-1){
                q.push({hp+mem[x][y],{x+1,y}});
            }
            if(y<m-1){
                q.push({hp+mem[x][y],{x,y+1}});
            }
        }
//         cout<<l<<' '<<r<<' '<<mid<<' '<<ok<<'\n';
        if(ok) l=mid+1;
        else r=mid;
    }
    cout<<l;
    return 0;
}