#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,ll) sort(a.begin(),a.end(),greater<ll>())
#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<ll,ll> pii;
typedef pair<ll,ll> pll;
typedef string str;
const ll maxn=2010;
ll matra[maxn][maxn];
ll h,w;
ll vh=-1;
ll vw=-1;
ll mh=-1;
ll mw=-1;
ll maxi=LLONG_MIN;
ll mini=LLONG_MAX;
bool obelezeno[maxn][maxn][2];
void obelezi(ll x,ll y,ll v,ll raz,ll 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(ll raz){
for(ll i=0;i<h;i++)
for(ll 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(ll i=0;i<h;i++) {for(ll j=0;j<w;j++) cout<<ll(obelezeno[i][j][0])<<" "; cout<<"\n";} cout<<"\n";
//for(ll i=0;i<h;i++) {for(ll j=0;j<w;j++) cout<<ll(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(ll i=0;i<h;i++){
ll koji=0;
for(ll 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(ll i=0;i<h;i++){
ll koji=1;
for(ll 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(ll j=0;j<w;j++){
ll koji=0;
for(ll 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(ll j=0;j<w;j++){
ll koji=1;
for(ll 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(ll i=0;i<h;i++)
for(ll 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;
}
}
ll l=0;
ll r=1e9;
ll res=0;
while(l<=r){
ll mid=l+(r-l)/2;
if(moze(mid)){
r=mid-1;
res=mid;
}else l=mid+1;
}
cout<<res;
}
int main(){
ios;
ll t=1;
//cin>>t;
while(t--) solve();
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
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 |
- |
| # |
결과 |
실행 시간 |
메모리 |
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 |
- |
| # |
결과 |
실행 시간 |
메모리 |
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 |
- |
