Submission

Score: 0

User: goine

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

Language: cpp

Time: 0.003 second

Submitted On: 2025-11-06 13:11:35

#include <iostream>
#include <map>
#include <utility>

int max_diff = 1e9; // Store minimum HP along paths
int x, y;

std::map<std::pair<int, int>, int> world_map;

void recur(int min_hp_so_far, int current_hp, std::pair<int, int> position) {
    current_hp += world_map[position];

    if (current_hp < min_hp_so_far) min_hp_so_far = current_hp;

    if (position.first == y && position.second == x) {
        if (min_hp_so_far < max_diff) max_diff = min_hp_so_far;
        return;
    }

    if (position.first < y)
        recur(min_hp_so_far, current_hp, {position.first + 1, position.second});
    if (position.second < x)
        recur(min_hp_so_far, current_hp, {position.first, position.second + 1});
}

int main() {
    std::cin >> y >> x;

    for (int i = 1; i <= y; i++) {
        for (int j = 1; j <= x; j++) {
            std::cin >> world_map[{i, j}];
        }
    }

    recur(0, 0, {1, 1});

    if (max_diff >= 0)
        std::cout << 1;
    else
        std::cout << -max_diff + 1;

    return 0;
}