Submission

Score: 0

User: august

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

Language: cpp

Time: 0.061 second

Submitted On: 2026-03-10 22:51:58

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

#define pi pair<int,int>

const int mx = 1e8;

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);
    int n,m;
    cin>> n>> m;

    vector<vector<int>> g(n+1, vector<int>(m+1));
    for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) cin>> g[i][j];

    vector<vector<pi>> mem(n+1, vector<pi>(m+1, {-mx, -mx}));// {pay, gain}
    
    mem[1][0] = {0,0};
    mem[0][1] = {0,0};

    for (int i=1; i<=n; i++) {
        for (int j=1; j<=m; j++) {
            pi up=mem[i-1][j], left=mem[i][j-1];

            if (up.first > left.first) mem[i][j] = up;
            else if (up.first == left.first) mem[i][j] = max(up,left);
            else mem[i][j] = left;

            if (g[i][j] >= 0) mem[i][j].second += g[i][j];
            else {
                mem[i][j].first += min(0, g[i][j] +mem[i][j].second);
                mem[i][j].second = max(0, g[i][j]+mem[i][j].second);
            }
           // cout<< "{ "<< mem[i][j].first<< ' '<< mem[i][j].second<< " }  ";
        }
       // cout<< '\n';
    }
    cout<< abs(mem[n][m].first)+1;
}