Submission

Score: 100

User: mantaggez

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

Language: cpp

Time: 0.061 second

Submitted On: 2026-03-11 23:03:41

#include <bits/stdc++.h>

using namespace std;
using pii = pair<int, int>;

const int nx = 1e3+5;

int n, m, a[nx][nx], dp[nx][nx];

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin >> n >> m;
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            cin >> a[i][j];
        }
    }
    
    for(int i=0;i<=n+1;i++) {
        for(int j=0;j<=m+1;j++) {
            dp[i][j] = 1e9;
        }
    }
    
    dp[n][m + 1] = dp[n + 1][m] = 1;

    for(int i=n;i>=1;i--) {
        for(int j=m;j>=1;j--) {
            int res = min(dp[i + 1][j], dp[i][j + 1]) - a[i][j];
            dp[i][j] = max(1, res);
        }
    }

    cout << dp[1][1];

    return 0;
}