#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int MAXN = 2000; int H, W, A[MAXN+10][MAXN+10], maxval=-987654321, minval=987654321; int B[MAXN+10][MAXN+10], l[MAXN+10][3], r[MAXN+10][3]; bool decide(int K) { int i, j; if(maxval-minval<=K) return true; int a=-1; for(i=1; i<=H; i++) { l[i][1]=l[i][2]=987654321; r[i][1]=r[i][2]=-1; for(j=1; j<=W; j++) { if(minval<=A[i][j] && A[i][j]<maxval-K) B[i][j]=1; else if(minval+K<A[i][j] && A[i][j]<=maxval) B[i][j]=2; else if(minval+K<A[i][j] && A[i][j]<maxval-K) return false; else B[i][j]=0; r[i][B[i][j]]=max(r[i][B[i][j]], j); l[i][B[i][j]]=min(l[i][B[i][j]], j); } } bool flag; int now; flag=true; now=0; for(i=1; i<=H; i++) { if(r[i][1]==-1 && r[i][2]==-1) continue; int s, e; if(r[i][1]!=-1 && r[i][2]!=-1) s=r[i][1], e=l[i][2]-1; else if(r[i][2]==-1) s=r[i][1], e=W; else if(r[i][1]==-1) s=0, e=l[i][2]-1; if(s>e) flag=false; if(e<now) flag=false; if(now<s) now=s; } if(flag) return true; flag=true; now=0; for(i=1; i<=H; i++) { if(r[i][1]==-1 && r[i][2]==-1) continue; int s, e; if(r[i][1]!=-1 && r[i][2]!=-1) s=r[i][2], e=l[i][1]-1; else if(r[i][1]==-1) s=r[i][2], e=W; else if(r[i][2]==-1) s=0, e=l[i][1]-1; if(s>e) flag=false; if(e<now) flag=false; if(now<s) now=s; } if(flag) return true; flag=true; now=0; for(i=H; i>=1; i--) { if(r[i][1]==-1 && r[i][2]==-1) continue; int s, e; if(r[i][1]!=-1 && r[i][2]!=-1) s=r[i][1], e=l[i][2]-1; else if(r[i][2]==-1) s=r[i][1], e=W; else if(r[i][1]==-1) s=0, e=l[i][2]-1; if(s>e) flag=false; if(e<now) flag=false; if(now<s) now=s; } if(flag) return true; flag=true; now=0; for(i=H; i>=1; i--) { if(r[i][1]==-1 && r[i][2]==-1) continue; int s, e; if(r[i][1]!=-1 && r[i][2]!=-1) s=r[i][2], e=l[i][1]-1; else if(r[i][1]==-1) s=r[i][2], e=W; else if(r[i][2]==-1) s=0, e=l[i][1]-1; if(s>e) flag=false; if(e<now) flag=false; if(now<s) now=s; } if(flag) return true; return false; } int main() { int i, j; scanf("%d%d", &H, &W); for(i=1; i<=H; i++) for(j=1; j<=W; j++) { scanf("%d", &A[i][j]); maxval=max(maxval, A[i][j]); minval=min(minval, A[i][j]); } int lo=0, hi=1e9; while(lo+1<hi) { int mid=lo+hi>>1; if(decide(mid)) hi=mid; else lo=mid; } printf("%d", hi); }

joioi.cpp: In function 'bool decide(int)':
joioi.cpp:18:6: warning: unused variable 'a' [-Wunused-variable]
  int a=-1;
      ^
joioi.cpp: In function 'int main()':
joioi.cpp:109:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid=lo+hi>>1;
           ~~^~~
joioi.cpp:98:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &H, &W);
  ~~~~~^~~~~~~~~~~~~~~~
joioi.cpp:101:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &A[i][j]);
   ~~~~~^~~~~~~~~~~~~~~~