fork(1) download
copy 
  1. // code by Deepak Verma
  2. #include <bits/stdc++.h>
  3. #include <cstdint>
  4. #define endl '\n'
  5. #define fast cin.tie(NULL);cout.tie(NULL);ios_base::sync_with_stdio(false)
  6. using namespace std;
  7. #define rep(i,l,r) for(int i=l;i<r;i++)
  8. #define repi(i,l,r) for(int i=l;i<=r;i++)
  9.  
  10. typedef long long ll ;
  11. typedef unsigned long long ull ;
  12. typedef pair<int,int> ii ;
  13. typedef vector<int> vi ;
  14. typedef vector<bool> vb ;
  15. typedef vector<char> vc ;
  16. typedef vector<double> vd ;
  17. typedef vector<vi> vvi ;
  18. typedef vector<ll> vll ;
  19. typedef vector<ii> vii ;
  20. typedef vector<char> vc ;
  21. typedef set<int> si ;
  22. typedef set<ll> sl ;
  23. typedef map<int,int> mii;
  24. typedef map<char,int> mci;
  25. const int mod = 1000*1000*1000+7 ;
  26. const ll inf = 1000000000000000000 ;
  27.  
  28. int n, m ;
  29. int inp[101][101] ;
  30. int memo[101][101] ;
  31. bool vis[101][101] ;
  32. int x, y, t ;
  33.  
  34. bool isval(int r, int c) {
  35.     if(r>0 && r<=n && c>0 && c<=m)
  36.         return 1 ;
  37.     else 
  38.         return 0 ;
  39. }
  40.  
  41. int dfs(int r, int c) {
  42.     if(memo[r][c] != -1) return memo[r][c] ;
  43.     if(vis[r][c]) return INT32_MAX ;
  44.  
  45.  
  46.     vis[r][c] = 1 ;
  47.     int ret = INT32_MAX ;
  48.  
  49.     if(isval(r-1, c)) {
  50.         int up = dfs(r-1, c) ;
  51.         if(up != INT32_MAX)
  52.             ret = min(ret, up) ;
  53.     }
  54.  
  55.     if(isval(r+1, c)) {
  56.         int down = dfs(r+1, c) ;
  57.         if(down != INT32_MAX)
  58.             ret = min(ret, down) ;
  59.     }
  60.  
  61.     if(isval(r, c-1)) {
  62.         int left = dfs(r, c-1) ;
  63.         if(left != INT32_MAX)
  64.             ret = min(ret, left) ;
  65.     }
  66.  
  67.     if(isval(r, c+1)) {
  68.         int right = dfs(r, c+1) ;
  69.         if(right != INT32_MAX)
  70.             ret = min(ret, right) ;
  71.     }
  72.     ret += inp[r][c] ;
  73.  
  74.     memo[r][c] = ret ;
  75.     return ret ;
  76. }
  77.  
  78. void solve() {
  79.     cin >> n >> m ;
  80.     memset(inp,-1, sizeof inp) ;
  81.     memset(memo,-1, sizeof memo) ;
  82.     memset(vis, 0, sizeof vis) ;
  83.  
  84.     repi(i,1,n) {
  85.         repi(j,1,m) cin >> inp[i][j] ;
  86.     }
  87.     cin >> x >> y >> t;
  88.     memo[x][y] = inp[x][y] ;
  89.  
  90.  
  91.     dfs(1, 1) ;
  92.  
  93.     // repi(i,1,n) {
  94.     //     repi(j,1,m) 
  95.     //         cout << memo[i][j] << ' ' ;
  96.     //     cout << endl ;
  97.     // }
  98.  
  99.     if(memo[1][1] <= t) {
  100.         cout << "YES\n" ;
  101.         cout << t - memo[1][1] << endl ;
  102.     }
  103.     else 
  104.         cout << "NO\n" ;
  105.  
  106. }
  107. int main() {
  108.     fast ;
  109. #ifndef ONLINE_JUDGE
  110.     freopen("input.txt", "r", stdin);
  111.     freopen("output.txt", "w", stdout);
  112. #endif
  113.  
  114.     int t ;
  115.     cin >> t ;
  116.     while(t--) {
  117.         solve() ;
  118.     }
  119. }
  120.  
Success #stdin #stdout 0s 4528KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/kinfzf
problem BYTESE1, based on SPOJ submission 27063888 (CPP), 2020-12-09 10:10:48
language:
C++14 (clang 8.0)
created:
3 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!