Submission

Score: 0

User: mantaggez

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

Language: cpp

Time: 0.004 second

Submitted On: 2026-03-11 22:40:11

#include <bits/stdc++.h>

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

const int nx = 1e3+5;

struct HP {
    int mn, cur;
};

int n, m, a[nx][nx];
HP 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];
        }
    }

    // dp[i][j] = {min, cur};

    for(int i=1;i<=n;i++) {
        if(dp[1][i - 1].cur + a[1][i] < 1) dp[1][i] = {dp[1][i - 1].mn + 1 - dp[1][i - 1].cur - a[1][i], 1};
        else dp[1][i] = {dp[1][i - 1].mn, dp[1][i - 1].cur + a[1][i]};

        if(dp[i - 1][1].cur + a[i][1] < 1) dp[i][1] = {dp[i - 1][1].mn + 1 - dp[i - 1][1].cur - a[i][1], 1};
        else dp[i][1] = {dp[i - 1][1].mn, dp[i - 1][1].cur + a[i][1]};
    }
    
    for(int i=2;i<=n;i++) {
        for(int j=2;j<=m;j++) {
            HP x, y;
            if(dp[i][j - 1].cur + a[i][j] < 1) x = {dp[i][j - 1].mn + 1 - dp[i][j - 1].cur - a[i][j], 1};
            else x = {dp[i][j - 1].mn, dp[i][j - 1].cur + a[i][j]};
            
            if(dp[i - 1][j].cur + a[i][j] < 1) y = {dp[i - 1][j].mn + 1 - dp[i - 1][j].cur - a[i][j], 1};
            else y = {dp[i - 1][j].mn, dp[i - 1][j].cur + a[i][j]};

            if(x.mn < y.mn) dp[i][j] = x;
            else if(x.mn == y.mn && x.cur > y.cur) dp[i][j] = x;
            else dp[i][j] = y;
        }
    }
    
    // cout << '\n';
    // for(int i=1;i<=n;i++) {
    //     for(int j=1;j<=m;j++) {
    //         cout << dp[i][j].mn << ' ' << dp[i][j].cur << '\t';
    //     }
    //     cout << '\n';
    // }
    
    cout << dp[n][m].mn;

    return 0;
}