Submission

Score: 100

User: SnowAveNode

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

Language: cpp

Time: 0.060 second

Submitted On: 2026-04-22 16:19:23

#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);

    ll n,m; cin>>n>>m;
    vector<vector<ll>> grid(n+1, vector<ll>(m+1));
    vector<ll> dp(m+2,INF); dp[m]=1;

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

    for(int i=n;i>=1;i--)
        for(int j=m;j>=1;j--) {
            if(i==n&&j==m){dp[j]=max(1LL,1LL-grid[i][j]);continue;}
            ll res=min(dp[j],dp[j+1]);
            dp[j]=max(1LL,res-grid[i][j]);
        }

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

    return 0;
}