This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<stdio.h>
#define N 2000
#define M 2000
int max(int i,int j){return i<j?j:i;}
int min(int i,int j){return i>j?j:i;}
int n, m, a[N][M], b[N][M], c[N][M], d[N][M], x, ii, jj;
int ok_(int a[][M], int ii, int jj)
{
static int down[M][N];
for(int i=0;i<m;++i)
{
down[i][0]=a[i][0];
for(int j=1;j<n;++j)
down[i][j]=min(down[i][j-1],a[j][i]);
}
int high = a[ii][jj];
static int sep[M];
int ptr=n-1;
for(int i=0;i<m;++i)
{
while(ptr>=0&&down[i][ptr]+x<high)--ptr;
sep[i]=ptr+1;
if(jj == i && sep[i] <= ii)
return 0;
}
int ioi_high=-1,ioi_low=1e9;
for(int i=0;i<m;++i)for(int j=sep[i];j<n;++j)
{
ioi_high=max(ioi_high,a[j][i]);
ioi_low=min(ioi_low,a[j][i]);
if(ioi_low+x<ioi_high)
return 0;
}
return 1;
}
int ok(int x0)
{
x = x0;
return ok_(a, ii, jj) || ok_(b, n-1-ii, jj) || ok_(c, ii, m-1-jj) || ok_(d, n-1-ii, m-1-jj);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=0;i<n;++i)for(int j=0;j<m;++j)
{
scanf("%d",a[i]+j), b[n-1-i][j]=a[i][j], c[i][m-1-j]=a[i][j], d[n-1-i][m-1-j]=a[i][j];
if(a[i][j]>a[ii][jj])ii=i,jj=j;
}
int lb=-1,ub=1e9;
while(ub-lb>1)
{
int mid=lb+(ub-lb)/2;
if(ok(mid))ub=mid;
else lb=mid;
}
printf("%d",ub);
}
Compilation message (stderr)
joioi.c: In function 'main':
joioi.c:52:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
52 | scanf("%d%d",&n,&m);
| ^~~~~~~~~~~~~~~~~~~
joioi.c:55:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
55 | scanf("%d",a[i]+j), b[n-1-i][j]=a[i][j], c[i][m-1-j]=a[i][j], d[n-1-i][m-1-j]=a[i][j];
| ^~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |