Submission #1213083

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213083		quocbaoo	The Kingdom of JOIOI (JOI17_joioi)	C++20	0 / 100	0 ms	324 KiB

joioi

#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)

joioi.cpp: In function 'int main()':
joioi.cpp:77:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |         freopen("peri.in","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
joioi.cpp:78:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |         freopen("peri.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 15
• Subtask 2: 0 / 45
• Subtask 3: 0 / 40