#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define xx first
#define yy second
#define srt(a) sort(a.begin(),a.end());
#define srtg(a,int) sort(a.begin(),a.end(),greater<int>())
#define lb(a,x) lower_bound(a.begin(),a.end(),x)
#define up(a,x) upper_bound(a.begin(),a.end(),x)
#define fnd(a,x) find(a.begin(),a.end(),x)
#define vstart auto startt=chrono::system_clock::now()
#define vend auto endd=chrono::system_clock::now()
#define vvreme chrono::duration<double> vremee=endd-startt
#define ios ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef string str;
const int maxn=2010;
int matra[maxn][maxn];
int h,w;
int vh=-1;
int vw=-1;
int mh=-1;
int mw=-1;
int maxi=INT_MIN;
int mini=INT_MAX;
bool obelezeno[maxn][maxn][2];
void obelezi(int x,int y,int v,int raz,int koji){
if(x<0 || y<0 || x>=h || y>=w) return;
//cout<<x<<" "<<y<<" "<<matra[x][y]<<" "<<v<<" "<<raz<<" "<<koji<<"\n";
if(abs(matra[x][y]-v)>raz) return;
if(obelezeno[x][y][koji]) return;
obelezeno[x][y][koji]=1;
obelezi(x+1,y,v,raz,koji);
obelezi(x-1,y,v,raz,koji);
obelezi(x,y+1,v,raz,koji);
obelezi(x,y-1,v,raz,koji);
}
bool moze(int raz){
for(int i=0;i<h;i++)
for(int j=0;j<w;j++) obelezeno[i][j][0]=obelezeno[i][j][1]=false;
obelezi(vh,vw,matra[vh][vw],raz,0);
obelezi(mh,mw,matra[mh][mw],raz,1);
//cout<<raz<<"\n";
//for(int i=0;i<h;i++) {for(int j=0;j<w;j++) cout<<int(obelezeno[i][j][0])<<" "; cout<<"\n";} cout<<"\n";
//for(int i=0;i<h;i++) {for(int j=0;j<w;j++) cout<<int(obelezeno[i][j][1])<<" "; cout<<"\n";} cout<<"\n\n";
bool dh1=false;
bool dv1=false;
bool dh2=false;
bool dv2=false;
bool tren=true;
for(int i=0;i<h;i++){
int koji=0;
for(int j=0;j<w;j++){
if(obelezeno[i][j][koji]) continue;
if(koji==1) tren=false;
else koji=1;
if(!obelezeno[i][j][koji]) tren=false;
}
}
if(tren) dh1=true;
tren=true;
for(int i=0;i<h;i++){
int koji=1;
for(int j=0;j<w;j++){
if(obelezeno[i][j][koji]) continue;
if(koji==0) tren=false;
else koji=0;
if(!obelezeno[i][j][koji]) tren=false;
}
}
if(tren) dh2=true;
tren=true;
for(int j=0;j<w;j++){
int koji=0;
for(int i=0;i<h;i++){
if(obelezeno[i][j][koji]) continue;
if(koji==1) tren=false;
else koji=1;
if(!obelezeno[i][j][koji]) tren=false;
}
}
if(tren) dv1=true;
tren=true;
for(int j=0;j<w;j++){
int koji=1;
for(int i=0;i<h;i++){
if(obelezeno[i][j][koji]) continue;
if(koji==0) tren=false;
else koji=0;
if(!obelezeno[i][j][koji]) tren=false;
}
}
if(tren) dv2=true;
return (dh1 || dh2) && (dv1 || dv2);
}
void solve(){
cin>>h>>w;
for(int i=0;i<h;i++)
for(int j=0;j<w;j++){
cin>>matra[i][j];
if(matra[i][j]>maxi){
maxi=matra[i][j];
vh=i;
vw=j;
}
if(matra[i][j]<mini){
mini=matra[i][j];
mh=i;
mw=j;
}
}
int l=0;
int r=1e9;
int res=0;
while(l<=r){
int mid=l+(r-l)/2;
if(moze(mid)){
r=mid-1;
res=mid;
}else l=mid+1;
}
cout<<res;
}
int main(){
ios;
int t=1;
//cin>>t;
while(t--) solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
