Submission

[PPPPPPPPPP-SSSS]

Score: 0

User: fluke

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

Language: cpp

Time: 0.058 second

Submitted On: 2025-03-22 11:01:07

#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 ffor(x,n) for(int x=1;x<=n;x++)
#define DB cout<<"\n";system("pause");
#define vec vector
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 = 2e9;
ll INF = 2e18;
int mod = 1e9 + 7;

int main(){
ios::sync_with_stdio(false);cin.tie(0); 
    int n,m;
    cin>>n>>m;
    vec <vec <int>> mp(n+1 , vec <int> (m+1)) , dp(n+1 , vec<int> (m+1));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            
            if(i == 1 && j == 1){
                cin>>mp[i][j];
            }
            else if(i == 1){
                cin>>mp[i][j];
                mp[i][j] += mp[i][j-1];
            }
            else if(j == 1){
                cin>>mp[i][j];
                mp[i][j] += mp[i-1][j];
            }
            else {
                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(i == 1 && j == 1){
                dp[i][j] = mp[i][j]*-1 + 1; 
            }
            else if(i == 1){
                dp[i][j] = max(mp[i][j]*-1 + 1 ,dp[i][j-1]);
            }
            else if(j == 1){
                dp[i][j] = max(mp[i][j]*-1 + 1 ,dp[i-1][j]); 
            }
            else {
                dp[i][j] = max(mp[i][j]*-1 + 1 ,min(dp[i-1][j] , dp[i][j-1]));
           }
        }
    }

    // ffor(i,n){
    //     ffor(j,m){
    //         cout<<dp[i][j]<<" ";
    //     }
    //     cout<<"\n";
    // }

    if(dp[n][m] <= 0)cout<<"1";
    else cout<<dp[n][m];

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