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>
using namespace std;
int h{};
int w{};
int max_alt{0};
int min_alt(1e9);
bool check_kingdom(int x, int country[2000][2000])
{
int border{w};
bool valid;
//min left top
if(country[0][0]-min_alt<=x)
{
valid=true;
for(int i=0; i<h; i++)
{
for(int j=0; j<w; j++)
{
if(j<border)
{
if(country[i][j]-min_alt>x) {border=j; j--;}
}
else
{
if(max_alt-country[i][j]>x)
{
valid=false;
break;
}
}
}
if(not valid) break;
}
if(valid) return true;
}
//min left bottom
border=w;
if(country[h-1][0]-min_alt<=x)
{
valid=true;
for(int i=h-1; i>=0; i--)
{
for(int j=0; j<w; j++)
{
if(j<border)
{
if(country[i][j]-min_alt>x) {border=j; j--;}
}
else
{
if(max_alt-country[i][j]>x)
{
valid=false;
break;
}
}
}
if(not valid) break;
}
if(valid) return true;
}
//max left top
border=w;
if(max_alt-country[0][0]<=x)
{
valid=true;
for(int i=0; i<h; i++)
{
for(int j=0; j<w; j++)
{
if(j<border)
{
if(max_alt-country[i][j]>x) {border=j; j--;}
}
else
{
if(country[i][j]-min_alt>x)
{
valid=false;
break;
}
}
}
if(not valid) break;
}
if(valid) return true;
}
//max left bottom
border=w;
if(max_alt-country[h-1][0]<=x)
{
valid=true;
for(int i=h-1; i>=0; i--)
{
for(int j=0; j<w; j++)
{
if(j<border)
{
if(max_alt-country[i][j]>x) {border=j; j--;}
}
else
{
if(country[i][j]-min_alt>x)
{
valid=false;
break;
}
}
}
if(not valid) break;
}
if(valid) return true;
}
return false;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin>>h>>w;
int country[2000][2000];
for(int i=0; i<h; i++)
{
for(int j=0; j<w; j++)
{
cin>>country[i][j];
max_alt=max(max_alt, country[i][j]);
min_alt=min(min_alt, country[i][j]);
}
}
int high=max_alt-min_alt;
int low=-1;
int mid;
while(high-low>1)
{
mid=(high+low)/2;
if(check_kingdom(mid, country)) high=mid;
else low=mid;
}
cout<<high;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |