SMMR-T092: Boss Room

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

typedef long long lli;

/// DR D DL
int ctrl[3] = {1, 0, -1};
int board[1010][1010];
int row, col;

vector<vector<int>> memo;
int KillBoss(int r, int c){
    if(memo[r][c] != -2){
        return memo[r][c];
    }
    if(r == row){
        if(board[r][c] < 5000){
            return memo[r][c] = 5500 - board[r][c];
        }
        return memo[r][c] = -1;
    } else {
        int mx = -1;
        for(int i = 0; i < 3; ++i){
            if(c + ctrl[i] > 0 && c + ctrl[i] <= col){
                if(KillBoss(r + 1, c + ctrl[i]) > board[r][c]){
                    mx = max(mx, KillBoss(r + 1, c + ctrl[i]));
                }
            }
        }
        return memo[r][c] = (mx == -1) ? -1 : mx + 500 - board[r][c];
    }
}

int main(){

    int x;

    scanf("%d %d", &row, &col);
    for(int i = 1; i <= row; ++i){
        for(int j = 1; j <= col;++j){
            scanf("%d", &x);
            board[i][j] = x;
        }
    }
    int mx = -1;
    memo.assign(row + 1, vector<int>(col + 1, -2));
    for(int i = 1; i <= col; ++i){
        mx = max(mx, KillBoss(1, i));
    }
    if(mx == -1){
        cout << -1;
    } else {
        cout << row * 500 + 5000 - mx;
    }

    return 0;
}