#include <bits/stdc++.h>
#define fi first
#define se second
#define lo long long
#define inf 1000000000
#define md 1000000007
#define li 1004
#define mp make_pair
#define pb push_back
#define pii pair<int , pair<int , int> >
using namespace std;
struct node{
int val, x, y;
};
bool operator < (node a, node b){
return a.val > b.val;
}
int n, m, A[li][li], vis[li][li], ans = - inf;
int yon1[6] = {1, - 1, 0, 0};
int yon2[6] = {0, 0, 1, - 1};
queue<node> q;
vector< pair<int , pair<int, int> > > v;
int main(){
scanf("%d %d", &n, &m);
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= m; j ++){
scanf("%d", &A[i][j]);
vis[i][j] = - inf;
v.pb(mp(A[i][j], mp(i, j)));
}
}
sort(v.begin(), v.end());
q.push((node){v.back().fi, v.back().se.fi, v.back().se.se});
v.pop_back();
while(! q.empty()){
node temp = q.front();
q.pop();
int val = temp.val;
int x = temp.x;
int y = temp.y;
if(vis[x][y] > val) continue;
ans = max(ans, val - A[x][y] - 1);
while((int)v.size() && v.back().fi == val){
q.push((node){v.back().fi, v.back().se.fi, v.back().se.se});
v.pop_back();
}
for(int i = 0; i <= 3 ; i ++){
int dx = x + yon1[i];
int dy = y + yon2[i];
if(dx >= 1 && dx <= n && dy >= 1 && dy <= n && val - 1 > vis[dx][dy]){
vis[dx][dy] = val - 1;
q.push((node){val - 1, dx, dy});
}
}
}
printf("%d\n", ans);
return 0;
}
Compilation message
maxcomp.cpp: In function 'int main()':
maxcomp.cpp:24:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &n, &m);
~~~~~^~~~~~~~~~~~~~~~~
maxcomp.cpp:27:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &A[i][j]);
~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
