Submission

[PPPP-SSSSSSSSSS]

Score: 0

User: mydKN

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

Language: cpp

Time: 0.003 second

Submitted On: 2025-03-30 23:20:56

#include<bits/stdc++.h>

using namespace std;

struct stc{
	int w, ui, uj;
	bool operator<(const stc& a) const{
		return w < a.w;
	}
};

const int maxn = 1005;
const int inf = 2e9;

int n, m;
int mp[maxn][maxn];
int low = 1, high = 0, res;

bool ok(int mid){
	priority_queue<stc> pq;
	vector<vector<int>> dist(n+5, vector<int>(m+5, -inf));
	dist[1][1] = mid;
	pq.push({mid + mp[1][1], 1, 1});
	while(!pq.empty()){
		auto [w, ui, uj] = pq.top();
		pq.pop();
		// cout << w << " " << ui << " " << uj << "\n";
		if(w <= 0) continue;
		if(ui == n && uj == m) return 1;
		if(ui+1 <= n && w + mp[ui+1][uj] > dist[ui+1][uj] && w + mp[ui+1][uj] > 0){
			dist[ui+1][uj] = w + mp[ui+1][uj];
			pq.push({dist[ui+1][uj], ui+1, uj});
		}
		if(uj+1 <= m && w + mp[ui][uj+1] > dist[ui][uj+1] && w + mp[ui][uj+1] > 0){
			dist[ui][uj+1] = w + mp[ui][uj+1];
			pq.push({dist[ui][uj+1], ui, uj+1});
		}
	}
	return 0;
}

int main(){
	ios_base::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 >> mp[i][j];
			if(mp[i][j] < 0) high += (-mp[i][j]);
		}
	}
	while(low <= high){
		int mid = (low + high) / 2;
		// cout << mid << "\n";
		if(ok(mid)){
			res = mid;
			high = mid - 1;
		}
		else{
			low = mid + 1;
		}
	}
	cout << res;
}