#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=-1, hi=1e9+10;
while(lo+1<hi)
{
int mid=lo+hi>>1;
if(decide(mid)) hi=mid;
else lo=mid;
}
printf("%d", hi);
}
Compilation message
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]);
~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
380 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
380 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
380 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
