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 <bits/stdc++.h>
#define L long long
using namespace std;
L n,m;
L totma=0,totmi=1000000000ll;
L a[2020][2020];
L c[2020][2020];
L nucolmax[2020][2020];
L xamlocun[2020][2020];
L nucolmin[2020][2020];
L nimlocun[2020][2020];
L colma[2020],colmi[2020];
void clear(){
L i;
for(i=1;i<=m;i++)
colma[i]=0,colmi[i]=1000000000ll;
}
void clear2(){
L i,j;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
c[i][j]=0;
}
bool ok(L dis){
L i,j;
clear();
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(a[i][j]>totmi+dis)
{
colma[j]=max(colma[j],i);
colmi[j]=min(colmi[j],i);
}
L now;
L mamin,mimax;
mamin=1000000000ll,mimax=0;
now=n+1;
for(j=m;j>=1;j--)
{
now=min(now,colmi[j]);
mamin=min(mamin,nimlocun[now][j]);
mimax=max(mimax,nucolmax[now-1][j]);
}
if(totma-mamin<=dis&&mimax-totmi<=dis) return 1;
mamin=1000000000ll,mimax=0;
now=n+1;
for(j=1;j<=m;j++)
{
now=min(now,colmi[j]);
mamin=min(mamin,nimlocun[now][j]);
mimax=max(mimax,nucolmax[now-1][j]);
}
if(totma-mamin<=dis&&mimax-totmi<=dis) return 1;
mamin=1000000000ll,mimax=0;
now=0;
for(j=1;j<=m;j++)
{
now=max(now,colma[j]);
mamin=min(mamin,nucolmin[now][j]);
mimax=max(mimax,xamlocun[now+1][j]);
}
if(totma-mamin<=dis&&mimax-totmi<=dis) return 1;
mamin=1000000000ll,mimax=0;
now=0;
for(j=m;j>=1;j--)
{
now=max(now,colma[j]);
mamin=min(mamin,nucolmin[now][j]);
mimax=max(mimax,xamlocun[now+1][j]);
}
if(totma-mamin<=dis&&mimax-totmi<=dis) return 1;
return 0;
}
int main()
{
scanf("%lld %lld",&n,&m);
L i,j;
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
scanf("%lld",&a[i][j]);
totma=max(totma,a[i][j]);
totmi=min(totmi,a[i][j]);
}
}
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
nucolmax[i][j]=max(nucolmax[i-1][j],a[i][j]);
for(i=n;i>=1;i--)
for(j=1;j<=m;j++)
xamlocun[i][j]=max(xamlocun[i+1][j],a[i][j]);
for(j=1;j<=m;j++)
nucolmin[0][j]=nimlocun[n+1][j]=1000000000ll;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
nucolmin[i][j]=min(nucolmin[i-1][j],a[i][j]);
for(i=n;i>=1;i--)
for(j=1;j<=m;j++)
nimlocun[i][j]=min(nimlocun[i+1][j],a[i][j]);
/*for(i=1;i<=n;i++,puts(""))
for(j=1;j<=m;j++)
printf("%lld ",nucolmax[i][j]);
puts("nucolmax");
for(i=1;i<=n;i++,puts(""))
for(j=1;j<=m;j++)
printf("%lld ",nucolmin[i][j]);
puts("nucolmin");
for(i=1;i<=n;i++,puts(""))
for(j=1;j<=m;j++)
printf("%lld ",xamlocun[i][j]);
puts("xamlocun");
for(i=1;i<=n;i++,puts(""))
for(j=1;j<=m;j++)
printf("%lld ",nimlocun[i][j]);
puts("nimlocun");
for(i=1;i<=n;i++,puts(""))
for(j=1;j<=m;j++)
printf("%lld ",nimlocun[i][j]);
puts("nimlocun");*/
L s=0,e=1000000000ll;
while(s<e)
{
L mid=(s+e)/2;
if(ok(mid)) e=mid;
else s=mid+1;
}
printf("%lld",s);
}
Compilation message (stderr)
joioi.cpp: In function 'int main()':
joioi.cpp:98:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
for(i=n;i>=1;i--)
^~~
joioi.cpp:102:3: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
for(j=1;j<=m;j++)
^~~
joioi.cpp:84:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld %lld",&n,&m);
~~~~~^~~~~~~~~~~~~~~~~~~
joioi.cpp:90:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld",&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... |