Submission #1000406

#	Time	Username	Problem	Language	Result	Execution time	Memory
1000406		Otalp	The Kingdom of JOIOI (JOI17_joioi)	C++14	100 / 100	2718 ms	102304 KiB

joioi

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define pii pair<int, int>
#define ff first
#define ss second

int a[2011][2011], b[2010][2010];
int mn, mx;
int n, m;

bool check(int x){
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            int ok2=(mx - a[i][j] <= x), ok1=(a[i][j] - mn <= x);
            if(!ok1 and !ok2) return 0;
            if(ok1 and ok2){
                b[i][j] = 0;
            }
            else if(ok1) b[i][j] = 1;
            else if(ok2) b[i][j] = 2;
        }
    }
    //cout<<x<<'\n';
    //for(int i=1; i<=n; i++){
    //    for(int j=1; j<=m; j++){
    //        cout<<b[i][j];
    //    }
    //    cout<<'\n';
    //}
    int ls = 0;
    for(int j=m; j>=1; j--){
        for(int i=ls+1; i<=n; i++){
            if(b[i][j] == 1){
                ls = max(ls, i);
            }
        }
        for(int i=1; i<=ls; i++){
            if(b[i][j] == 2){
                //cout<<a[i][j]<<'\n';
                return 0 ;
            }
        }
    }
    return 1;
}

int solve(int N, int M){
    n = N;
    m = M;
    int l=0, r=2e9 + 1;
    while(l + 1 < r){
        int mid=(l+r)/2;
        if(check(mid))  r = mid;
        else l = mid;
    }
    return r;
}

void rotate(){
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            b[m - j + 1][i] = a[i][j];
        }
    }
    swap(n, m);
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            a[i][j] = b[i][j];
        }
    }
    //for(int i=1; i<=n; i++){
    //    for(int j=1; j<=m; j++){
    //        cout<<a[i][j]<<' ';
    //    }
    //    cout<<'\n';
    //}

}


void solve(){
    cin>>n>>m;
    mn = 1e9;
    mx = 0;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            cin>>a[i][j];
            mn = min(mn, a[i][j]);
            mx = max(mx, a[i][j]);
        }
    }
    int ans = solve(n, m);
    rotate();
    ans = min(ans, solve(n, m));
    rotate();
    ans = min(ans, solve(n, m));
    rotate();
    ans = min(ans, solve(n, m));
    cout<<ans<<'\n';
}


signed main(){
    solve();
}

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