Submission

[PPPPPPPP-SSSSSS]

Score: 0

User: yumiKuri

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

Language: cpp

Time: 0.075 second

Submitted On: 2025-04-01 10:36:18

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

const int N = 1001;
int dp[N][N][2];
int table[N][N];

int main(){
    ios_base::sync_with_stdio(0), cin.tie(0);

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

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

    for(int i = 1; i <= n; i++) dp[i][0][0] = dp[i][0][1] = -1e9;
    for(int i = 1; i <= m; i++) dp[0][i][0] = dp[0][i][1] = -1e9;

    

    dp[1][1][1] = dp[1][1][0] = table[1][1];

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(i == 1 and j == 1) continue;
            int up = dp[i-1][j][0] + table[i][j];
            int neg_up = dp[i-1][j][1];
            if(up < neg_up) neg_up = up;

            int left = dp[i][j-1][0] + table[i][j];
            int neg_left = dp[i][j-1][1];
            if(left < neg_left) neg_left = left;

            if(neg_left > neg_up){
                dp[i][j][0] = left;
                dp[i][j][1] = neg_left;
            }
            else if(neg_left == neg_up){
                dp[i][j][0] = max(left, up);
                dp[i][j][1] = neg_left;
            }
            else{
                dp[i][j][0] = up;
                dp[i][j][1] = neg_up;
            }
        }
    }

    /*for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cout << dp[i][j][0] << ' ';
        }
        cout << '\n';
    }

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cout << dp[i][j][1] << ' ';
        }
        cout << '\n';
    }*/

    if(dp[n][m][1] >= 0) cout << 1;
    else cout << dp[n][m][1]*-1 + 1;


}