Submission

[PPPP-SSSSSSSSSS]

Score: 0

User: fluke

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

Language: cpp

Time: 0.002 second

Submitted On: 2025-03-22 10:41:45

#include <bits/stdc++.h>
#define ll long long 
#define f first 
#define s second  
#define pii pair<int,int>
#define emb emplace_back
#define em emplace
#define all(x) x.begin(),x.end()
#define sp <<" "<<
#define DB cout<<"\n";system("pause");
using namespace std;

int mod = 1e9 + 7;
int inf = 2e9;
ll INF = 2e18;

int di[]={0,1,0,-1,1,1,-1,-1};
int dj[]={1,0,-1,0,1,-1,1,-1};


int main(){
ios::sync_with_stdio(false);cin.tie(0);
    int n,m;
    cin>>n>>m;
    vector <vector <int>> mp(n+1 , vector <int> (m+1 ,-1*inf)) , dp(n+1 , vector <int> (m+1,inf));
    mp[0][1] = 0;
    mp[1][0] = 0;
    dp[0][1] = 0;
    dp[1][0] = 0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>mp[i][j];
            mp[i][j] += max(mp[i-1][j] , mp[i][j-1]);
        }
    }

    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(mp[i][j] <= 0){
                dp[i][j] = max(abs(mp[i][j]) + 1 , min(dp[i-1][j] , dp[i][j-1]));
            } 
            else {
                dp[i][j] = min(dp[i-1][j] , dp[i][j-1]);
            }
        }
    }
    // for(int i=1;i<=n;i++){
    //     for(int j=1;j<=m;j++){
    //        cout<<dp[i][j]<<" ";
    //     }
    //     cout<<"\n";
    // }

    cout<<dp[n][m];
    




}
/*
 2 3
 -3 -6 -3
 2 2 -3

  4 3
  -3 -6 -3
  2 2 -3 
  -8 -8 -8
 1 1 1
*/