Submission #1162327

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162327		brover29	The Kingdom of JOIOI (JOI17_joioi)	C++17	100 / 100	3643 ms	94692 KiB

joioi

#include <bits/stdc++.h>
//qwerty47924692
using namespace std;
using ll = long long;
const ll N=2005;
const string br="617283";
#define sz(a)(ll)a.size()
#define f first
#define s second
ll  n,m,a[N][N],b[N][N],mn=1e18,mx=-1e18,c[N][N];
bool is_good(){
    bool ok=1;
    for(ll i=1;i<=n;i++){
        ll cnt=0;
        for(ll j=1;j<=m;j++){
            ok&=(c[i][j]&b[i][j])==(c[i][j]);
            cnt+=(c[i][j]!=c[i][j-1]);
        }
        ok&=(cnt<=2);
    }return ok;
}void clr(){
    for(ll i=1;i<=n;i++){
        for(ll j=1;j<=m;j++){
            c[i][j]=2;
        }
    }
}
bool check(ll x){
    for(ll i=1;i<=n;i++){
        for(ll j=1;j<=m;j++){
            b[i][j]=0;
            b[i][j]|=(a[i][j]<=mn+x);
            b[i][j]|=2*(a[i][j]>=mx-x);
          //  cout<<b[i][j];
            if(!b[i][j])return 0;
        }//cout<<'\n';
    }clr();
    ll cur=m;
    for(ll i=1;i<=n;i++){

        for(ll j=1;j<=cur;j++){
            if(!(b[i][j]&1)){
                cur=j-1;
                break;
            }
            c[i][j]=1;
        }
    }
    if(is_good())return 1;
    clr();
    cur=m;
    for(ll i=n;i>=1;i--){
        for(ll j=1;j<=cur;j++){
            if(!(b[i][j]&1)){
                cur=j-1;
                break;
            }
            c[i][j]=1;
        }
    }
    if(is_good())return 1;
    clr();
    cur=n;
    for(ll j=1;j<=m;j++){
        for(ll i=1;i<=cur;i++){
            if(!(b[i][j]&1)){
                cur=i-1;
                break;
            }
            c[i][j]=1;
        }
    }if(is_good())return 1;
    clr();
    cur=n;
    for(ll j=m;j>=1;j--){
        for(ll i=1;i<=cur;i++){
            if(!(b[i][j]&1)){
                cur=i-1;
                break;
            }
            c[i][j]=1;
        }
    }if(is_good())return 1;
    return 0;

}void mirror(){
    for(ll i=1;i<=n;i++){
        for(ll j=1;j<=m/2;j++){
            swap(a[i][j],a[i][m-j+1]);
        }
    }for(ll i=1;i<=n/2;i++){
        for(ll j=1;j<=m;j++){
            swap(a[n-i+1][j],a[i][j]);
        }
    }
}
ll solve(){
    ll l=1,r=1e9;
    while(l<r){
        ll mid=(r+l)>>1;
        if(check(mid))r=mid;
        else l=mid+1;
    }
    mirror();
    return l;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin>>n>>m;
    for(ll i=1;i<=n;i++){
        for(ll j=1;j<=m;j++){
            cin>>a[i][j];
            mn=min(mn,a[i][j]);
            mx=max(mx,a[i][j]);
        }
    }
    cout<<min(solve(),solve());
}

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