Submission

[PPPPPPPPPPPPPPP]

Score: 100

User: qwerty

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

Language: cpp

Time: 0.086 second

Submitted On: 2025-03-17 20:35:15

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

int main(){
    cin.tie(0)->sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    vector<vector<int>> path(n+1, vector<int>(m+1, 0));
    // start at (1, 1)
    for (int i = 1 ; i <= n ; i++){
        for (int j = 1 ; j <= m ; j++){
            cin >> path[i][j];
        }
    }

    vector<vector<int>> dp(n+2, vector<int>(m+2, INT_MAX));
    dp[n + 1][m] = dp[n][m + 1] = 1;
    for (int i = n ; i > 0 ; i--) {
        for (int j = m ; j > 0 ; j--) {
            if (i==n && j == m) {
                dp[n][m] = max(1, 1-path[n][m]);
                continue;
            }
            int minn = min(dp[i+1][j], dp[i][j+1]);
            dp[i][j] = max(1, minn-path[i][j]);
        }
    }

    cout << dp[1][1];
}
// 2 3 -3 -6 -3 2 2 -3