#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
#define int long long
#define ld long double
#define pii pair<int,int>
#define rand() abs((rand()<<15)|rand())
#define randll() abs(((long long)rand()<<30)|rand())
const int MOD = 998244353;
int grid[2005][2005];
int vis[2005][2005];
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
long long seed;
asm("rdtsc" : "=A"(seed));
srand(seed);
int n, m;
cin >> n >> m;
multiset<int> rem;
memset(grid, -1, sizeof(grid));
int mi=1,mj=1;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
cin >> grid[i][j];
if(grid[i][j] > grid[mi][mj])
mi=i,mj=j;
rem.insert(grid[i][j]);
}
}
int aMax = grid[mi][mj];
int aMin = grid[mi][mj];
int ans = 1ll<<40;
priority_queue<pair<int, pair<int, int>>> pq;
pq.push({grid[mi][mj], {mi, mj}});
while(!pq.empty()) {
int i = pq.top().second.first;
int j = pq.top().second.second;
grid[i][j] = pq.top().first;
pq.pop();
aMin = min(aMin, grid[i][j]);
rem.erase(rem.find(grid[i][j]));
if(rem.empty()) break;
ans = min(ans, max(aMax-aMin, *rem.rbegin()-*rem.begin()));
grid[i][j] = -1;
if(grid[i-1][j ]!=-1) {pq.push({grid[i-1][j ], {i-1, j }}); grid[i-1][j ]=-1; };
if(grid[i+1][j ]!=-1) {pq.push({grid[i+1][j ], {i+1, j }}); grid[i+1][j ]=-1; };
if(grid[i ][j-1]!=-1) {pq.push({grid[i ][j-1], {i , j-1}}); grid[i ][j-1]=-1; };
if(grid[i ][j+1]!=-1) {pq.push({grid[i ][j+1], {i , j+1}}); grid[i ][j+1]=-1; };
}
cout << ans << endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
31868 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
31868 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
31868 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
