Submission

Score: 0

User: PIXIX

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

Language: cpp

Time: 1.087 second

Submitted On: 2026-03-19 15:50:44

#include <climits>
#include <iostream>
#include <vector>
using namespace std;

// int solve(vector<vector<int>> &grid){
//     int row = grid.size();
//     int col = grid[0].size();
//     vector<vector<int>> dp(row + 1,vector<int>(col + 1,INT_MAX));
//     dp[row - 1][col] = 1;
//     dp[row][col - 1] = 1;

//     for(int i = row - 1;i >= 0;i--){
//         for(int j = col - 1;j >= 0;j--){
        
//             dp[i][j] = min(1 , min(dp[i+1][j],dp[i][j+1]) - grid[i][j]);

//         }
//     }
//     return dp[0][0];

// }



bool check(vector<vector<int>> &grid,int row,int col ,long long maxHp,vector<vector<int>> &memo){
     if(row >= grid.size() || col >= grid[0].size()) return false;
    if(row == grid.size() - 1 && col == grid[0].size() - 1){
        if(maxHp + grid[row][col] > 0) return true;
        return false;
    }
    if(maxHp + grid[row][col] <= 0) return false;
    if(memo[row][col] >= maxHp + grid[row][col]) return false;
    memo[row][col] = maxHp + grid[row][col];
    
    return check(grid,row + 1,col,maxHp + grid[row][col],memo) || check(grid,row,col + 1,maxHp + grid[row][col],memo);
}


int main (int argc, char *argv[]) {

    int n , m; cin>>n>>m;

    vector<vector<int>> grid(n+1,vector<int>(m+1,0));

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

    long long left = 1;
    long long right = LLONG_MAX;
    long long ans = right;
    long long mid = left + (right - left) / 2;

    while(left <= right){
        mid = left + (right - left) / 2;
        vector<vector<int>> memo(grid.size(),vector<int>(grid[0].size(),-1)); 
        if(check(grid,1,1,mid,memo)){
            ans = mid;
            right = mid - 1;
        }else {
            left = mid + 1;
        }
    }
    cout << ans;

    return 0;
}