Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define MAX 1002
- #define ll long long
- using namespace std;
- ll n, m, v, c, e;
- ll mat[MAX][MAX], memo[MAX][MAX];
- ll dp(ll i, ll j) {
- if(i == 0 && j == m-c) return mat[i][j];
- if(i < 0 || j < 0) return (1<<30);
- if(memo[i][j]) return memo[i][j];
- if(j == 0) return memo[i][j] = mat[i][j] + min(dp(i-1, j), dp(i-1, j+1));
- if(j == m-1) return memo[i][j] = mat[i][j] + min(dp(i-1, j), dp(i-1, j-1));
- if(j > 0 && j < m-1) return memo[i][j] = mat[i][j] + min(dp(i-1, j), min(dp(i-1, j+1), dp(i-1, j-1)));
- }
- int main() {
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- cin >> n >> m >> v;
- for(ll i = 0; i < n; i++) {
- for(ll j = 0; j < m; j++) {
- cin >> mat[i][j];
- }
- }
- memset(memo, 0, sizeof(memo));
- cin >> c >> e;
- ll res = dp(n-1, e-1);
- if(res < v) cout << v-res;
- else cout << -1;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement