#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;
ll a[maxn][maxn];
int main(void){
fastio;
int h, w;
cin>>h>>w;
ll 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 = -1, ok = INF + 5;
while(ng + 1 < ok){
int m = (ng + ok) / 2;
int bad = 0;
vector<int> mnx(h + 1, INF), mn2x(h + 1, INF);
for(int i = 0; i < h; i++){
for(int j = 0; j < w; j++){
if(a[i][j] > mn + m && a[i][j] < mx - m) bad = 1;
if(a[i][j] > mn + m) mnx[i] = min(mnx[i], j);
if(a[i][j] < mx - m) mn2x[i] = min(mn2x[i], j);
}
}
if(bad){
ng = m;
continue;
}
vector<int> lst(mn2x), lsb(mn2x), grt(mnx), grb(mnx);
for(int i = 1; i < h; i++) lst[i] = min(lst[i], lst[i - 1]), grt[i] = min(grt[i], grt[i - 1]);
for(int i = h - 2; i >= 0; i--) lsb[i] = min(lsb[i], lsb[i + 1]), grb[i] = min(grb[i], grb[i + 1]);
vector<int> gd(4, 1);
for(int i = 0; i < h; i++){
for(int j = 0; j < w; j++){
if(a[i][j] > mn + m){
if(j > lst[i]) gd[0] = 0;
if(j > lsb[i]) gd[1] = 0;
}
if(a[i][j] < mx - m){
if(j > grt[i]) gd[2] = 0;
if(j > grb[i]) gd[3] = 0;
}
}
}
if(gd[0] + gd[1] + gd[2] + gd[3]) ok = m;
else ng = m;
}
cout<<ok<<"\n";
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
468 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
468 KB |
Output is correct |
| 10 |
Correct |
0 ms |
348 KB |
Output is correct |
| 11 |
Correct |
0 ms |
348 KB |
Output is correct |
| 12 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
468 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
468 KB |
Output is correct |
| 10 |
Correct |
0 ms |
348 KB |
Output is correct |
| 11 |
Correct |
0 ms |
348 KB |
Output is correct |
| 12 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
468 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
468 KB |
Output is correct |
| 10 |
Correct |
0 ms |
348 KB |
Output is correct |
| 11 |
Correct |
0 ms |
348 KB |
Output is correct |
| 12 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
