Advertisement
Alexvans

Dungeon Lvl.3

Jun 12th, 2017
69
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.84 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define MAX 1002
  3. #define ll long long
  4. using namespace std;
  5.  
  6. ll n, m, v, c, e;
  7. ll mat[MAX][MAX], memo[MAX][MAX];
  8.  
  9. ll dp(ll i, ll j) {
  10.     if(i == 0 && j == m-c) return mat[i][j];
  11.     if(i < 0 || j < 0) return (1<<30);
  12.     if(memo[i][j]) return memo[i][j];
  13.     if(j == 0) return memo[i][j] = mat[i][j] + min(dp(i-1, j), dp(i-1, j+1));
  14.     if(j == m-1) return memo[i][j] = mat[i][j] + min(dp(i-1, j), dp(i-1, j-1));
  15.     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)));
  16. }
  17.  
  18. int main() {
  19.     ios_base::sync_with_stdio(0);
  20.     cin.tie(0);
  21.     cout.tie(0);
  22.  
  23.     cin >> n >> m >> v;
  24.     for(ll i = 0; i < n; i++) {
  25.         for(ll j = 0; j < m; j++) {
  26.             cin >> mat[i][j];
  27.         }
  28.     }
  29.     memset(memo, 0, sizeof(memo));
  30.     cin >> c >> e;
  31.     ll res = dp(n-1, e-1);
  32.     if(res < v) cout << v-res;
  33.     else cout << -1;
  34. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement