Submission

Score: 0

User: yypp

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

Language: cpp

Time: 0.005 second

Submitted On: 2026-03-25 17:43:30

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

int mp[1005][1005],n,m,inf=-1e9;
int wk[1005][1005];
pair<int,int> bf[1005][1005];
int wx[] = {1,0};
int wy[] = {0,1};

void dp(int x,int y) {
    //printf("%d %d\n",x,y);
    if (x==n&&y==m) {
        return;
    }
    for (int i=0;i<2;i++) {
        int ix = x+wx[i]; int iy = y+wy[i];
        //printf("-> %d %d\n",ix,iy);
        //printf("= %d %d %d\n",wk[x][y],mp[ix][iy],wk[ix][iy]);
        //printf("ck %d %d %d %d %d\n",ix>=1,ix<=n,iy>=1,iy<=m,wk[x][y]+mp[ix][iy]<wk[ix][iy]);
        //printf("ck2 %d %d %d %d\n",ix,n,iy,m);
        if (ix>=1&&ix<=n&&iy>=1&&iy<=m&&wk[x][y]+mp[ix][iy]>wk[ix][iy]) {
            //cout << "in\n";
            wk[ix][iy] = wk[x][y]+mp[ix][iy];
            bf[ix][iy] = {x,y};
            dp(ix,iy);
        }
    }
}

int main() {
    int tx,ty;
    int ans=INT_MAX;
    cin >> n >> m;
    for (int i=1;i<=n;i++) {
        for (int j=1;j<=m;j++) {
            cin >> mp[i][j];
            wk[i][j] = inf;
        }
    }
    wk[1][1] = mp[1][1];
    //cout << dp(1,1) << "\n";
    dp(1,1);
    /*
    for (int i=1;i<=n;i++) {
        for (int j=1;j<=m;j++) {
            cout << wk[i][j] << " ";
        }
        cout << "\n";
    }
    */
    int x=n,y=m;
    while(x!=0&&y!=0) {
        //cout << x << " " << y << "\n";
        ans = min(ans,wk[x][y]);
        tx=x; ty=y;
        x = bf[tx][ty].first; y = bf[tx][ty].second;
    }
    cout << 1-ans;
}