Submission

Score: 100

User: Dark_kingdom

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

Language: cpp

Time: 0.167 second

Submitted On: 2026-10-13 14:48:10

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
	int N,M;
	cin>>N>>M;
	
	vector<vector<int>> A(N, vector<int>(M));
	
	
	for(int i = 0; i<N; i++)
	{
		for(int j = 0;j<M; j++)
		{
			cin>>A[i][j];
		}
	}
	
	vector<vector<int>> dp(N, vector<int>(M));
	
	dp[N-1][M-1] = max(1, 1 - A[N-1][M-1]);
	
	for(int i = N-1; i>=0; i--)
	{
		for(int j = M-1; j>=0; j--)
		{
			if(i == N-1 && j == M-1)
			{
				continue;
			}
			
			int need;
			
			if(i == N-1)
			{
				need = dp[i][j+1];
			}
			
			else if((j == M-1))
			{
				need = dp[i+1][j];
			}
			
			else
			{
				need = min(dp[i+1][j], dp[i][j+1]);
			}
			
			dp[i][j] = max(1, need - A[i][j]);
		}
	}
	
	cout<< dp[0][0]<<"\n";
	
	return 0;
}