Submission

Score: 0

User: august

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

Language: cpp

Time: 1.047 second

Submitted On: 2026-03-10 22:32:10

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

#define int long long

const int INF = 1e7+7;
#define pi pair<int,int>


int32_t main() {
    cin.tie(0)->sync_with_stdio(0);
    int n,m;
    cin>> n>> m;

    vector<vector<int>> g(n+1, vector<int>(m+1));
    for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) cin>> g[i][j];

    int l=1, r=INF;

    int di[2] = {0, 1}, dj[2] = {1, 0};

    while (l<=r) {
        int mid=(l+r)/2;

        if (mid + g[1][1] <= 0) l=mid+1;
        
        priority_queue<pair<int, pi>, vector<pair<int, pi>>, less<pair<int, pi>>> pq;
        pq.push({mid+g[1][1], {1, 1}});
        vector<vector<int>> h(n+1, vector<int>(m+1, -3*INF));
        h[1][1] = mid+g[1][1];

        bool ok=false;
        while (!pq.empty() && !ok) {
            pair<int, pi> cur = pq.top();
            pq.pop();

            int ch=cur.first, i=cur.second.first, j=cur.second.second;

            if (h[i][j] > ch) continue;

            for (int e=0; e<2; e++) {
                int ni=i+di[e], nj=j+dj[e];
                if (ni<1 || nj<1 || ni>n || nj>m || h[i][j] + g[ni][nj] <= 0) continue;

                if (h[ni][nj] < h[i][j] + g[ni][nj]) {
                    h[ni][nj] = h[i][j] + g[ni][nj];
                    if (ni == n && nj == m) {
                        ok = true;
                        break;
                    }
                    pq.push({h[ni][nj], {ni,nj}});
                }
            }
        }
        if (h[n][m] <= 0) l=mid+1;
        else r=mid-1;
        
    }
    cout<< l;
}