Submission

Score: 100

User: Quaoar

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

Language: cpp

Time: 0.060 second

Submitted On: 2026-03-05 23:08:41

//ตั้งสมาธิ เสกความรู้ ปวดขี้ aka coding dijkdjasiud's algorithm by only memory to erase this code out of head and write ts again
#include <bits/stdc++.h>
using namespace std;

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

    int n , m;
    cin >> n >> m;

    vector <vector <int>> map(n + 2, vector<int>(m + 2 , 0));
    vector <vector <int>> dp(n + 2, vector<int>(m  + 2, INT_MAX));

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

    dp[n][m] = max(1 , 1 - map[n][m]);

    for (int i = n ; i >= 0 ; i--){
        for (int j = m ; j >= 0 ; j--){
            if (i == n && j == m) continue;

            int need = min(dp[i + 1][j] , dp[i][j + 1]) - map[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;
}