Submission

[PPPP-SSSSSSSSSS]

Score: 0

User: lufychop

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

Language: cpp

Time: 0.018 second

Submitted On: 2025-03-14 14:37:43

#include <bits/stdc++.h>

using namespace std;

int main(void)
{
	vector<vector<long long>> v(1001,vector<long long>(1001,-1e18));
	vector<vector<long long>> dp(1001,vector<long long>(1001));
	long long n,m,l,r,ans;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>v[i][j];
		}
	}
	l=0;
	r=1e11;
	while(l<=r)
	{
		bool ch=false;
		long long mid=l+(r-l)/2,t1,t2;
		queue<pair<long long,long long>> q;
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
			{
				dp[i][j]=-1e18;
			}
		}
		dp[1][1]=mid+v[1][1];
		if(dp[1][1]<=0)
		{
			l=mid+1;
			continue;
		}
		q.push({1,1});
		while(!q.empty())
		{
			t1=q.front().first;
			t2=q.front().second;
			q.pop();
			if(t1==n && t2==m)
			{
				ch=true;
				break;
			}
			if(t1+1<=n)
			{
				if(dp[t1][t2]+v[t1+1][t2]>0 && dp[t1+1][t2]<dp[t1][t2]+v[t1+1][t2])
				{
					dp[t1+1][t2]=dp[t1][t2]+v[t1+1][t2];
					q.push({t1+1,t2});
				}
			}
			if(t2+1<=m)
			{
				if(dp[t1][t2]+v[t1][t2+1]>0 && dp[t1][t2+1]<dp[t1][t2]+v[t1][t2+1])
				{
					dp[t1][t2+1]=dp[t1][t2]+v[t1][t2+1];
					q.push({t1,t2+1});
				}
			}
		}
		if(ch)
		{
			//ans=mid;
			r=mid-1;
		}
		else
		{
			l=mid+1;
		}
	}
	cout<<l;
	return 0;
}	
/*
2 3
-3 -6 -3
2 2 -3

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