Submission

[PPPP-SSSSSSSSSS]

Score: 0

User: hmmm

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

Language: cpp

Time: 0.008 second

Submitted On: 2025-03-13 23:13:50

#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int a[N][N],dp[N][N],n,m;

inline bool chk(int x){
	if(x+a[1][1]<=0){
//		cout << "==\n";
		return false;
	}
	memset(dp,-0x3f,sizeof dp);
//	dp[1][1]=x;
	dp[0][1]=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			dp[i][j]=max(dp[i-1][j],dp[i][j-1])+a[i][j];
			if(i==1 && j==1) dp[i][j]+=x;
			if(dp[i][j]<=0) dp[i][j]=-1e9;
		}
	}
//	for(int i=1;i<=n;i++){
//		for(int j=1;j<=m;j++){
//			cout << dp[i][j] << ' ';
//		}
//		cout << "\n";
//	}
//	cout << dp[n][m] << "--\n";
	if(dp[n][m]>0) return true;
	else return false;
}

int main(){
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin >> a[i][j];
		}
	}
	int l=0,r=N*N*10*10;
	while(l<r){
		int mid=(l+r)/2;
//		cout << mid << "\n";
		if(chk(mid)==true) r=mid;
		else l=mid+1;
	}
	cout << l;
}