Submission

Score: 0

User: Kx

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

Language: cpp

Time: 0.002 second

Submitted On: 2026-03-18 08:49:49

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

const int mn = -(1e4 + 1);

int n, m;
vector<vector<int>> mp;
vector<vector<int>> mem;

int main() {
    cin >> n >> m;
    mp.assign(n, vector<int>(m)); for(int i = 0; i < n; ++i) {for(int j = 0; j < m; ++j) {cin >> mp[i][j];}}

    mem.assign(n, vector<int>(m, mn));
    mem = mp;

    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < m; ++j) {
            if(i > 0 && j > 0) mem[i][j] = max(mem[i - 1][j], mem[i][j - 1]) + mp[i][j];
            if(i > 0 && j == 0) mem[i][j] += mem[i - 1][j];
            if(i == 0 && j > 0) mem[i][j] += mem[i][j - 1];
        }
    }

    vector<int> dist, min_v;
    int i = n - 1, j = m - 1;
    while(i > 0 || j > 0) {
        dist.push_back(mp[i][j]);
        int v = mem[i][j] - mp[i][j];
        if(mem[i - 1][j] == v) {
            i--;
        } else if(mem[i][j - 1] == v) {
            j--;
        }
    }
    dist.push_back(mp[i][j]);

    int res = 0;
    for(int i = 0; i < (int)dist.size(); ++i) {
        if(dist[i] < 0) {
            for(int j = i; j < (int)dist.size(); ++j) {
                res += dist[j];
            }
            break;
        }
    }

    res = abs(res) + 1;
    reverse(dist.begin(), dist.end());
    int test = res;
    for(int i = 0; i < (int)dist.size(); ++i) {
        test += dist[i];
        while(test <= 0) {
            res++, test++;
        }
    }

    cout << res;

    return 0;
}