Submission

[-SSSSSSSSSSSSSS]

Score: 0

User: Nozomi_boundfortokyo

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

Language: cpp

Time: 0.003 second

Submitted On: 2025-03-20 11:35:28

#include <bits/stdc++.h>
using namespace std;
int n,m;
typedef long long ll;
ll arr[1001][1001];
ll dp[1001][1001];
ll history[1001][1001];

int main()
{
	cin>>n>>m;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			cin>>arr[i][j];
		}
	}
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			if(i==0 && j==0)
			{
				dp[i][j]=arr[i][j];
				history[i][j]=arr[i][j];
			}
			else if(i==0)
			{
				dp[i][j]=dp[i][j-1]+arr[i][j];
				history[i][j]=min(dp[i][j],history[i][j-1]);
			}
			else if(j==0)
			{
				dp[i][j]=dp[i-1][j]+arr[i][j];
				history[i][j]=min(dp[i][j],history[i-1][j]);				
			}
			else
			{
				if(dp[i-1][j]>dp[i][j-1])
				{
					dp[i][j]=dp[i-1][j]+arr[i][j];
					history[i][j]=min(dp[i][j],history[i-1][j]);
				}
				else if(dp[i-1][j]<dp[i][j-1])
			    {
					dp[i][j]=dp[i][j-1]+arr[i][j];
					history[i][j]=min(dp[i][j],history[i][j-1]);			    	
				}
				else
				{
					dp[i][j]=dp[i][j-1]+arr[i][j];
					history[i][j]=min(dp[i][j],min(history[i][j-1],history[i-1][j]));
				}
			}
		}
	}
	if(history[n-1][m-1]<0)
	{
		cout<<1;
		return 0;
	}
	cout<<abs(history[n-1][m-1])+1;
}