Submission

[PPPPPPPPPP-SSSS]

Score: 0

User: fluke

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

Language: cpp

Time: 0.073 second

Submitted On: 2025-03-22 13:56:23

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

int di[] = {0,1,0,-1,1,1,-1,-1};
int dj[] = {1,0,-1,0,1,-1,1,-1};
int inf = 1e9;
ll INF = 1e18;

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)) , maxhp(n+1 , vector <int> (m+1)), dp(n+1,vector <int> (m+1));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>mp[i][j];
            mp[i][j] = mp[i][j]*-1;
            
            if(i == 1 && j == 1)maxhp[i][j] = mp[i][j];
            else if(i == 1)maxhp[i][j] = mp[i][j] + maxhp[i][j-1];
            else if(j == 1)maxhp[i][j] = mp[i][j] + maxhp[i-1][j];
            else maxhp[i][j] = mp[i][j] + min(maxhp[i][j-1] , maxhp[i-1][j]);
     
        }
    }

    // DB
    // ffor(i,n){
    //     ffor(j,m){
    //         cout<<maxhp[i][j]<<" ";
    //     }
    //     cout<<"\n";
    // }
    // DB
    
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(i == 1 && j == 1)dp[i][j] = max(1 , maxhp[i][j] + 1);
            else if(i == 1)dp[i][j] = max({1 , maxhp[i][j] + 1 , dp[i][j-1]});
            else if(j == 1)dp[i][j] = max({1 , maxhp[i][j] + 1 , dp[i-1][j]});
            else dp[i][j] = max({1, maxhp[i][j] + 1,  min(dp[i-1][j] , dp[i][j-1])});
        }
    }    
    
    // ffor(i,n){
    //     ffor(j,m){
    //         cout<<dp[i][j]<<" ";
    //     }
    //     cout<<"\n";
    // }
    // DB
    cout<<dp[n][m];
}   
/*
4 3
-3 -6 -3
2 2 -3
-8 -8 -8
1 1 1
*/