#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//#include<bits/extc++.h>
//__gnu_pbds
int he[2005][2005];
int h,w;
vector<pair<int,int> > minn;
bool walked[2005][2005];
int dx[4] = {0,0,-1,1};
int dy[4] = {-1,1,0,0};
int Maxn,Minn;
int cnt;
int minnn = INT_MAX;
int maxnn = INT_MIN;
int minbound[2005];
int maxbound[2005];
bool check(int d){
for(int i=1;i<=h;i++) minbound[i]=0;
for(int i=1;i<=h;i++) maxbound[i]=w+1;
for(int i=1;i<=h;i++){
for(int j=1;j<=w;j++){
if(he[i][j]>minnn+d) break;
minbound[i]=j;
}
for(int j=w;j>=1;j--){
if(he[i][j]<maxnn-d) break;
maxbound[i]=j;
}
}
bool works = 1;
for(int i=1;i<=h;i++){
if(maxbound[i]-minbound[i]>1){works=0;break;}
}
if(works) return 1;
//cout<<d<<"ok\n";
for(int i=1;i<=h;i++) minbound[i]=w+1;
for(int i=1;i<=h;i++) maxbound[i]=0;
for(int i=1;i<=h;i++){
for(int j=w;j>=1;j--){
if(he[i][j]>minnn+d) break;
minbound[i]=j;
}
for(int j=1;j<=w;j++){
if(he[i][j]<maxnn-d) break;
maxbound[i]=j;
}
}
works = 1;
for(int i=1;i<=h;i++){
if(minbound[i]-maxbound[i]>1){works=0;break;}
}
if(works) return 1;
return 0;
}
int main(){
ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>h>>w;
for(int i=1;i<=h;i++){
for(int j=1;j<=w;j++){
cin>>he[i][j];
minnn = min(minnn,he[i][j]);
maxnn = max(maxnn,he[i][j]);
}
}
int l = 0;int r = 1e9+5;
while(r-l>1){
int mid = (l+(r-l)/2);
// cout<<check(mid)<<" "<<mid<<"\n";
if(check(mid)) r = mid;
else l = mid;
}
cout<<r<<"\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
