Submission

[PPPP-SSSSSSSSSS]

Score: 0

User: Jibhong

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

Language: cpp

Time: 0.005 second

Submitted On: 2025-03-31 09:48:46

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

const int INF = 2e9;
using pii = pair<int, int>;

int mem[1005][1005];
vector<vector<int>> dp(1005, vector<int>(1005, -INF));
int n, m;

bool is_valid(int mid) {
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, -INF));
    dp[1][1] = mid + mem[1][1];  // Start with initial health
    
    if (dp[1][1] <= 0) return false;  // If we start with negative or zero, it's invalid
    
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (i == 1 && j == 1) continue;
            if (i > 1 && dp[i - 1][j] > 0) {
                dp[i][j] = max(dp[i][j], dp[i - 1][j] + mem[i][j]);
            }
            if (j > 1 && dp[i][j - 1] > 0) {
                dp[i][j] = max(dp[i][j], dp[i][j - 1] + mem[i][j]);
            }
        }
    }
    return dp[n][m] > 0;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> mem[i][j];
        }
    }

    int l = 0, r = INF;
    while (l < r) {
        int mid = (l + r) / 2;
        if (is_valid(mid)) r = mid;
        else l = mid + 1;
    }
    cout << l << '\n';
    return 0;
}