Submission

Score: 100

User: Shangbin

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

Language: cpp

Time: 0.165 second

Submitted On: 2026-01-13 20:57:53

//Problem = https://grader.gchan.moe/problemset/c2_st65_knight
#include <bits/stdc++.h>
using namespace std;

#define pii pair<int, int>

const int maxmn = 1e3 + 5, inf = 1e9;
int n, m, a[maxmn][maxmn], dp[maxmn][maxmn], start_hp;

int main(){
    cin >> n >> m;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            cin >> a[i][j];
        }
    }
    dp[1][1] = a[1][1];
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            if (i == 1 && j == 1) continue;
            if (i == 1) dp[1][j] = dp[1][j-1];
            else if (j == 1) dp[i][1] = dp[i-1][1];
            else dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
            dp[i][j] += a[i][j];
            //cout << dp[i][j] << ' ';
        }
        //cout << '\n';
    }
    int i = n, j = m;
    start_hp = dp[i][j];
    while (i > 1 || j > 1){
        if (i > 1 && dp[i][j] == dp[i-1][j] + a[i][j]) i--;
        else if (j > 1 && dp[i][j] == dp[i][j-1] + a[i][j]) j--;
        start_hp = min(dp[i][j], start_hp);
    }
    if (start_hp > 0) cout << 1;
    else cout << 1 - start_hp;
}