#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define endl "\n"
#define fr first
#define sc second
#define sz size()
#define ins insert
#define bc back()
#define str string
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
//void fre(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
void start(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
const ll inf=1e18+7;
const ll mod=1e9;
const ll N=2e3+7;
const ld eps=1e-9;
ll xx[4]={1,-1,0,0},yy[4]={0,0,1,-1};
bool vis[N][N],good[N][N],need[N][N];
ll a[N][N],mx=0,mn=inf;
ll n,m;
ll i,j;
bool check(ll mid){
ll lim=0;
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
if(a[i][j]<mx-mid)lim=max(lim,j+1);
}
for(j=1;j<=lim;j++){
if(a[i][j]>mn+mid)return false;
}
lim=0;
}
return true;
}
void flip1(){
for(j=1;j<=m;++j)
for(i=1;i<=n/2;++i)
swap(a[n-i+1][j],a[i][j]);
}
void flip2(){
for(i=1;i<=n;++i)
for(j=1;j<=m/2;j++)
swap(a[i][m-j+1],a[i][j]);
}
ll bin(){
ll l=0,r=mx-mn;
while(r-l>1){
ll mid=(l+r)/2;
if(check(mid))r=mid;
else l=mid;
}
return r;
}
void solve(){
cin>>n>>m;
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
cin>>a[i][j];
mx=max(mx,a[i][j]);
mn=min(mn,a[i][j]);
}
}
if(mn==mx){
cout<<0<<endl;
return;
}
ll ans=mx-mn;
ans=min(ans,bin());
flip1();
ans=min(ans,bin());
flip2();
ans=min(ans,bin());
flip1();
ans=min(ans,bin());
cout<<ans<<endl;
}
signed main(){
start();
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
ll t=1;
//cin>>t;
while(t--) solve();
}
/*
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
