Submission

Score: 100

User: SnowAveNode

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

Language: cpp

Time: 0.061 second

Submitted On: 2026-04-19 11:55:48

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

const int nx = 1e5 + 5, MOD = 1e9 + 7, inf = 2e9; const ll INF = 4e18;

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);

    int N, M; cin >> N >> M;
    vector<vector<int>> A(N + 1, vector<int>(M + 1));
    vector<vector<int>> dp(N + 1, vector<int>(M + 1));

    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= M; j++)
            cin >> A[i][j];

    for (int i = N; i >= 1; i--) {
        for (int j = M; j >= 1; j--) {
            if (i == N && j == M) {
                dp[i][j] = max(1, 1 - A[i][j]);
            } else if (i == N) {
                dp[i][j] = max(1, dp[i][j + 1] - A[i][j]);
            } else if (j == M) {
                dp[i][j] = max(1, dp[i + 1][j] - A[i][j]);
            } else {
                dp[i][j] = max(1, min(dp[i + 1][j], dp[i][j + 1]) - A[i][j]);
            }
        }
    }

    cout << dp[1][1] << '\n';

    return 0;
}