Submission

Score: 0

User: navysrimuang

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

Language: cpp

Time: 0.003 second

Submitted On: 2026-03-12 21:31:06

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int a[1005][1005];
pair<int,int> par[1005][1005];

int main(){
	
	int n,m;
	cin >> n >> m;
	vector<vector<int>> dp(n,vector<int>(m,-1e9));

	for(int i = 0;i<n;i++){
		for(int j = 0;j<m;j++){
			cin >> a[i][j];
		}
	}
	dp[0][0] = a[0][0];
	par[0][0] = {-1,-1};
	for(int i = 0;i<n;i++){
		for(int j = 0;j<m;j++){
			if(!i && !j) continue;
			if(i){
				if(dp[i-1][j] + a[i][j] > dp[i][j]){
					dp[i][j] = dp[i-1][j] + a[i][j];
					par[i][j] = {i-1,j};					
				}
			}
			if(j){
				if(dp[i][j-1] + a[i][j] > dp[i][j]){
					dp[i][j] = dp[i][j-1] + a[i][j];
					par[i][j] = {i,j-1};
				}
			}
		}
	}
	int mn = dp[0][0];
	int i = n-1,j = m-1;
	while(i != 0 || j != 0){
		mn = min(mn,dp[i][j]);
		auto [ii,jj] = par[i][j];
		i = ii;
		j = jj;
	}

	if(mn > 0) cout << 0;
	else{
		cout << -mn + 1;
	}
	cout << "\n";
	return 0;
}