#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define lowbit(x) x&-x
const int N = 998244353;
const int INF = 1e9;
const int maxn = 2005;
int a[maxn][maxn];
int main(void){
fastio;
int h, w;
cin>>h>>w;
int mn = INF, mx = 0;
for(int i = 0; i < h; i++){
for(int j = 0; j < w; j++){
cin>>a[i][j];
mn = min(mn, a[i][j]);
mx = max(mx, a[i][j]);
}
}
int ng = 0, ok = INF;
while(ng + 1 < ok){
int m = (ng + ok) / 2;
int bad = 0;
//smaller on top
int give = 0, get = 0, ndall = 0, ndz = 0;
for(int j = 0; j < w; j++){
if(a[0][j] > mn + m && give) ndall = 1;
if(a[h- 1][j] < mx - m && get) ndz = 1;
int c1 = 0, c2 = 0;
for(int i = 0; i < h; i++){
if(a[i][j] > mn + m){
c2++, get = 1;
if(ndz) bad = 1;
}
else if(a[i][j] < mx - m){
c1++, give = 1;
if(c2) bad = 1;
if(ndall) bad = 1;
}
}
}
if(!bad){
ok = m;
continue;
}
bad = give = get = ndall = ndz = 0;
// smaller at the bottom
for(int j = 0; j < w; j++){
if(a[h - 1][j] > mn + m && give) ndall = 1;
if(a[0][j] < mx - m && get) ndz = 1;
int c1 = 0, c2 = 0;
for(int i = 0; i < h; i++){
if(a[i][j] > mn + m){
c2++, get = 1;
if(ndz) bad = 1;
if(c1) bad = 1;
}
else if(a[i][j] < mx - m){
c1++, give = 1;
if(ndall) bad = 1;
}
}
}
if(bad) ng = m;
else ok = m;
}
cout<<ok<<"\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
