Submission #67867006

---

Source Code Expand

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

#define ll long long	
const ll mod = 1e9 + 7;

vector<pair<int, int>> dirsFuture = {{1, 0}, {0, 1}};
vector<pair<int, int>> dirsPast = {{-1, 0}, {0, -1}};

bool check(int x, int y, int n, int m) {
	if(x < 0 || y < 0 || x >= n || y >= m)
		return false;

	return true;
}

void solve() {
	ll h, w;
	cin >> h >> w;

	vector<vector<ll>> arr(h, vector<ll> (w));
	for(int i = 0; i < h; i++) {
		for(int j = 0; j < w; j++) {
			cin >> arr[i][j];
		}
	}

	vector<ll> price(h + w - 1);
	for(int i = 0; i < h + w - 1; i++) {
		cin >> price[i];
	}

	price.begin(), price.end();

	vector<vector<ll>> dp(h, vector<ll> (w, -1e12));
	vector<vector<int>> vis(h, vector<int> (w, 0));
	vector<vector<pair<int, int>>> par(h, vector<pair<int, int>> (w, {-1, -1}));
	queue<pair<ll, pair<ll, ll>>> q;

	q.push({0, {0, 0}});

	while(!q.empty()) {
		auto node = q.front(); q.pop();

		ll idx = node.first;
		ll x = node.second.first;
		ll y = node.second.second;

		// cout << x << " " << y << ": " << dp[x][y] << " --> ";

		if(vis[x][y] == 1)
			continue;
		vis[x][y] = 1;

		if(x == 0 && y == 0) {
			dp[x][y] = arr[x][y] - price[idx];
		}
		else {
			for(auto dir : dirsPast) {
				int nx = x + dir.first;
				int ny = y + dir.second;

				if(check(nx, ny, h, w)) {
					if(dp[x][y] < dp[nx][ny]) {
						dp[x][y] = dp[nx][ny];
						par[x][y] = {nx, ny};
					}
				}
			}


			dp[x][y] += arr[x][y] - price[idx];
		}


		

		for(auto dir : dirsFuture) {
			int nx = x + dir.first;
			int ny = y + dir.second;

			if(check(nx, ny, h, w)) {
				q.push({idx + 1, {nx, ny}});
			}
		}
	}

	// for(auto x : dp) {
	// 	for(auto y : x) {
	// 		cout << y << " ";
	// 	}
	// 	cout << '\n';
	// }
	// cout << '\n';

	// cout << dp[h - 1][w - 1] << '\n';


	pair<int, int> curr = {h - 1, w - 1};
	ll ans = 0;
	while(curr != make_pair(-1, -1)) {
		ans = min(ans, dp[curr.first][curr.second]);
		curr = par[curr.first][curr.second];
	}

	cout << abs(ans) << '\n';
}

int main() {
	#ifndef ONLINE_JUDGE  
    	freopen("input.txt", "r", stdin); 
    	freopen("output.txt", "w", stdout); 
    #endif 
    
	int t = 1;
	// cin >> t;

	for(int i = 0; i < t; i++) {
		solve();
	}
}     

Submission Info

Compile Error

Main.cpp: In function ‘void solve()’:
Main.cpp:33:20: warning: ignoring return value of ‘constexpr std::vector<_Tp, _Alloc>::iterator std::vector<_Tp, _Alloc>::begin() [with _Tp = long long int; _Alloc = std::allocator<long long int>; iterator = std::vector<long long int>::iterator]’, declared with attribute ‘nodiscard’ [-Wunused-result]
   33 |         price.begin(), price.end();
      |         ~~~~~~~~~~~^~
In file included from /usr/include/c++/12/vector:64,
                 from /usr/include/c++/12/functional:62,
                 from /usr/include/x86_64-linux-gnu/c++/12/bits/stdc++.h:71,
                 from Main.cpp:1:
/usr/include/c++/12/bits/stl_vector.h:868:7: note: declared here
  868 |       begin() _GLIBCXX_NOEXCEPT
      |       ^~~~~

Judge Result