# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1213083 | quocbaoo | The Kingdom of JOIOI (JOI17_joioi) | C++20 | 0 ms | 324 KiB |
#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
using namespace std;
int mi=1e9,li,lj,a[2004][2003],n,m,dd[2004][2004],lu;
bool check(int mid){
for (int i=1;i<=n;i++){
for (int j=1;j<=m;j++) dd[i][j]=0;
}
li=lu;
while (li<=n){
if (a[li][lj]>mi+mid) return false;
dd[li][lj]=1;li++;
}
li=lu;
while (li>=1){
if (a[li][lj]>mi+mid) break;
dd[li][lj]=1;li--;
}
for (int j=lj+1;j<=m;j++){
for (int i=n;i>=1;i--){
if (a[i][j]<=mi+mid) dd[i][j]=1;
else break;
}
}
for (int j=lj-1;j>=1;j--){
for (int i=n;i>=1;i--){
if (a[i][j]<=mi+mid) dd[i][j]=1;
else break;
}
}
int bd=1e9,kt=0;
for (int i=1;i<=n;i++){
for (int j=1;j<=m;j++){
if (dd[i][j]==0) bd=min(bd,a[i][j]),kt=max(kt,a[i][j]);
}
}
if (kt-bd<=mid) return true;
////////
for (int i=1;i<=n;i++){
for (int j=1;j<=m;j++) dd[i][j]=0;
}
li=lu;
while (li>=1){
if (a[li][lj]>mi+mid) return false;
dd[li][lj]=1;li--;
}
li=lu;
while (li<=n){
if (a[li][lj]>mi+mid) break;
dd[li][lj]=1;li++;
}
for (int j=lj+1;j<=m;j++){
for (int i=1;i<=n;i++){
if (a[i][j]<=mi+mid) dd[i][j]=1;
else break;
}
}
for (int j=lj-1;j>=1;j--){
for (int i=1;i<=n;i++){
if (a[i][j]<=mi+mid) dd[i][j]=1;
else break;
}
}
bd=1e9;kt=0;
for (int i=1;i<=n;i++){
for (int j=1;j<=m;j++){
if (dd[i][j]==0) bd=min(bd,a[i][j]),kt=max(kt,a[i][j]);
}
}
if (kt-bd<=mid) return true;
return false;
}
int main(){
if (fopen("peri.in","r")){
freopen("peri.in","r",stdin);
freopen("peri.out","w",stdout);
}
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>m;
for (int i=1;i<=n;i++){
for (int j=1;j<=m;j++) {
cin>>a[i][j];
if (a[i][j]<mi){
mi=a[i][j];
li=i;lj=j;
}
}
}
int l=0,r=1e9,ans=-1;lu=li;
// cout<<check(20)<<endl;
while (l<=r){
int mid=(l+r)/2;
if (check(mid)) ans=mid,r=mid-1;
else l=mid+1;
}
cout<<ans;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |