#include<bits/stdc++.h>
#define F first
#define S second
#define MAX 3005
#define oo 1e18
#define mod 1000000007
#define fast_in ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);cout.setf(ios::fixed);cout.precision(0);
using namespace std;
typedef long long ll;
#define pll pair<ll , ll>
#define vll vector<ll>
#define vvll vector<vll>
#define vpll vector<pll>
ll tmn[5][MAX][MAX],tmx[5][MAX][MAX],n,a[MAX][MAX],m;
map<ll,ll> mp;
vll v;
ll OK(ll x,ll z){
//cout<<x<<": ";
ll r=oo,mx=0,c=0;
for(int i=1;i<=n;i++){
while(c+1<=m && tmn[1][i][c+1]<x)c++;
mx=max(mx,tmx[0][i][c]);
}r=min(r,mx);
//cout<<mx<<" ";
mx=0;c=0;
for(int i=n;i>0;i--){
while(c+1<=m && tmn[1][i][c+1]<x)c++;
mx=max(mx,tmx[0][i][c]);
}r=min(r,mx);
//cout<<mx<<" ";
mx=0;c=m+1;
for(int i=1;i<=n;i++){
while(c-1>=0 && tmn[0][i][c-1]<x)c--;
mx=max(mx,tmx[1][i][c]);
}r=min(r,mx);
//cout<<mx<<" ";
mx=0;c=m+1;
for(int i=n;i>0;i--){
while(c-1>=m && tmn[0][i][c-1]<x)c--;
mx=max(mx,tmx[1][i][c]);
}r=min(r,mx);
//cout<<mx<<"\n";
if(z==1)return max(abs(r-v[0]),abs(v.back()-x));
if(abs(r-v[0])>=abs(v.back()-x))return 0;
return 1;
}
int main(){
fast_in
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
if(mp[a[i][j]]==0){
mp[a[i][j]]=1;
v.push_back(a[i][j]);
}
}
tmx[0][i][0]=tmx[1][i][m+1]=0;
tmn[0][i][0]=tmn[1][i][m+1]=oo;
for(int j=1;j<=m;j++){
tmx[0][i][j]=max(tmx[0][i][j-1],a[i][j]);
tmn[0][i][j]=min(tmn[0][i][j-1],a[i][j]);
}
for(int j=m;j>0;j--){
tmx[1][i][j]=max(tmx[1][i][j+1],a[i][j]);
tmn[1][i][j]=min(tmn[1][i][j+1],a[i][j]);
//cout<<tmn[1][i][j]<<" ";
}//cout<<"\n";
}sort(v.begin(),v.end());
if(v.size()==1){cout<<0;return 0;}
ll p=1,f=v.size();//cout<<f<<" ";
while(abs(p-f)!=1){
ll md=(p+f)/2;//cout<<md<<":";
if(OK(v[md],0)==1)p=md;
else f=md;
}
cout<<min(OK(v[p],1),OK(v[f],1));
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
8660 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
8660 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
8660 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
