Submission

Score: 0

User: Ecir

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

Language: cpp

Time: 0.004 second

Submitted On: 2025-10-04 12:31:58

#include <bits/stdc++.h>
using namespace std;
using ll=long long int;
int arr[1009][1009];
vector<vector<int>> dp(1009,vector<int>(1009,INT_MIN));
int val[1009][1009];
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int sy,sx;cin >> sy >> sx;
    for(int i=1;i<=sy;i++){
        for(int j=1;j<=sx;j++) cin >> arr[i][j];
    }
    dp[0][1]=0;
    dp[1][0]=0;
    for(int i=1;i<=sy;i++){
        for(int j=1;j<=sx;j++){
            if(min(dp[i-1][j],val[i-1][j]+arr[i][j]) > min(dp[i][j-1],val[i][j-1]+arr[i][j])){
                dp[i][j]=min(dp[i-1][j],val[i-1][j]+arr[i][j]);
                val[i][j]+=val[i-1][j]+arr[i][j];
            }
            else{
                dp[i][j]=min(dp[i][j-1],val[i][j-1]+arr[i][j]);
                val[i][j]+=val[i][j-1]+arr[i][j];
            }
        }
    }
    if(dp[sy][sx]<=0) cout << abs(dp[sy][sx])+1;
    else cout << 1;
    return 0;
}