#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];
int proces[2005][2005];
int dfs(int i, int j) {
vis[i][j] = 1;
int x = 1;
if(grid[i+1][j ] != -1 && vis[i+1][j ]==0) x += dfs(i+1, j );
if(grid[i-1][j ] != -1 && vis[i-1][j ]==0) x += dfs(i-1, j );
if(grid[i ][j+1] != -1 && vis[i ][j+1]==0) x += dfs(i , j+1);
if(grid[i ][j-1] != -1 && vis[i ][j-1]==0) x += dfs(i , j-1);
return x;
}
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}});
proces[mi][mj] = 1;
while(!pq.empty()) {
int i = pq.top().second.first;
int j = pq.top().second.second;
grid[i][j] = pq.top().first;
int storeGrid = grid[i][j];
pq.pop();
if((grid[i+1][j ]==-1)||
(grid[i-1][j ]==-1)||
(grid[i ][j+1]==-1)||
(grid[i ][j-1]==-1)) {
grid[i][j] = -1;
int x = 0;
memset(vis, 0, sizeof(vis));
if(grid[i+1][j ]!=-1) x=dfs(i+1, j );
else if(grid[i-1][j ]!=-1) x=dfs(i-1, j );
else if(grid[i ][j+1]!=-1) x=dfs(i , j+1);
else if(grid[i ][j-1]!=-1) x=dfs(i , j-1);
grid[i][j] = storeGrid;
if(x+1 != rem.size()) {
proces[i][j]=0;
continue;
}
}
aMin = min(aMin, storeGrid);
rem.erase(rem.find(storeGrid));
if(rem.empty()) break;
ans = min(ans, max(aMax-aMin, *rem.rbegin()-*rem.begin()));
grid[i][j] = -1;
// for(int i = 1; i <= n; i++)
// for(int j = 1; j <= m; j++)
// cerr << grid[i][j] << " \n"[j==m];
// cerr << aMax-aMin << " " << *rem.rbegin()-*rem.begin() << endl;
// cerr << endl;
if(grid[i-1][j ]!=-1 && proces[i-1][j ]==0) {pq.push({grid[i-1][j ], {i-1, j }}); proces[i-1][j ]=1; };
if(grid[i+1][j ]!=-1 && proces[i+1][j ]==0) {pq.push({grid[i+1][j ], {i+1, j }}); proces[i+1][j ]=1; };
if(grid[i ][j-1]!=-1 && proces[i ][j-1]==0) {pq.push({grid[i ][j-1], {i , j-1}}); proces[i ][j-1]=1; };
if(grid[i ][j+1]!=-1 && proces[i ][j+1]==0) {pq.push({grid[i ][j+1], {i , j+1}}); proces[i ][j+1]=1; };
}
cout << ans << endl;
}
Compilation message
joioi.cpp: In function 'int main()':
joioi.cpp:76:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(x+1 != rem.size()) {
~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
463 ms |
63352 KB |
Output is correct |
| 2 |
Incorrect |
470 ms |
63464 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
463 ms |
63352 KB |
Output is correct |
| 2 |
Incorrect |
470 ms |
63464 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
463 ms |
63352 KB |
Output is correct |
| 2 |
Incorrect |
470 ms |
63464 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
