Submission

Score: 100

User: Kikii

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

Language: cpp

Time: 0.061 second

Submitted On: 2026-03-11 09:26:31

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n,k;
    cin >> n >> k;
    vector<vector<long long>> grid(n, vector<long long> (k));
    for(int i = 0; i < n; i ++){
        for(int j = 0; j < k; j ++){
            cin >> grid[i][j];
        }
    }
    vector<vector<long long>> dp(n, vector<long long> (k));
    dp[n-1][k-1] = max(1LL, 1LL - grid[n-1][k-1]);
    for(int i = k-2; i >= 0; i --){
        dp[n-1][i] = max(1LL, dp[n-1][i+1] - grid[n-1][i]);
    }

    for(int i = n-2; i >= 0; i --){
        dp[i][k-1] = max(1LL, dp[i+1][k-1] - grid[i][k-1]);
    }

    for(int i = n-2; i >= 0; i --){
        for(int j = k-2; j >= 0; j --){
            int mi = min(dp[i+1][j],dp[i][j+1]);
            dp[i][j] = max(1LL, mi - grid[i][j]);
        }
    }
    cout << dp[0][0];
}