Submission

Score: 100

User: Quaoar

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

Language: cpp

Time: 0.170 second

Submitted On: 2026-03-05 22:05:48

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

vector <vector<int>> arr;
vector <vector<int>> dp;


int main(){
    int n , m;
    cin >> n >> m;

    arr.resize(n + 2, vector<int>(m + 2, 0));
    dp.resize(n + 2, vector<int>(m + 2, INT_MAX));

    for (int i = 1 ; i <= n ; i++){
        for (int j = 1 ; j <= m ; j++){
            cin >> arr[i][j];
        }
    }

    dp[n][m] = max(1, 1 - arr[n][m]);
    
    for (int i = n ; i >= 1 ; i--){
        for (int j = m ; j >= 1 ; j--){
            if (i == n && j == m) continue;
            int need = min(dp[i + 1][j] , dp[i][j + 1]) - arr[i][j];
            dp[i][j] = max(1 , need);
        }
    }
    /*
    for (int i = 1 ; i <= n ; i++){
        for (int j = 1 ; j <= m ; j++){
            cout << dp[i][j] << " ";
        }
        cout << "\n";
    }
    */
    cout << dp[1][1];
    return 0;
}