Submission #51563

#	Time	Username	Problem	Language	Result	Execution time	Memory
51563		Flying_dragon_02	The Kingdom of JOIOI (JOI17_joioi)	C++17	100 / 100	2544 ms	63644 KiB

joioi

#include<bits/stdc++.h>

using namespace std;

const int inf = 1e9;
int n,m,pos[2005];
int a[2005][2005],ans = inf,mn = inf,mini[2005][2005],maxi[2005][2005],temp[2005][2005];

void _rotate(){
    int numi=1,numj=1;
    for(int i = 1 ; i <= m;i++){
        for(int j = n;j >= 1;j--){
            temp[numi][numj] = a[j][i];
            numj++;
        }
        numj=1;
        numi++;
    }
    swap(n,m);
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=m;j++)
            a[i][j] = temp[i][j];
    }
}

bool check(int val){
    for(int i = 1;i <= n;i++){
        pos[i] = m + 1;
        for(int j = 1;j <= m;j++){
            if(a[i][j] > mn + val){pos[i] = j; break;}
        }
    }
    for(int i = 1;i <= n;i++){
        mini[i][m+1] = inf;
        maxi[i][m+1] = 1;
        for(int j = m;j >= 1;j--){
            mini[i][j] = min(a[i][j],mini[i][j+1]);
            maxi[i][j] = max(a[i][j],maxi[i][j+1]);
        }
        mini[i][0] = mini[i][1]; maxi[i][0] = maxi[i][1];
    }
    int curMin = inf,curMax = 1,cur = m+1;
    for(int i = 1;i <= n;i++){
        cur = min(cur,pos[i]);
        curMin = min(curMin,mini[i][cur]);
        curMax = max(curMax,maxi[i][cur]);
    }
    if(curMax - curMin<=val)
        return 1;
    else
        return 0;
}

void solve(){
    int l = 0,r = inf - 1,mid;
    while(l<r){
        mid = (l+r)/2;
        if(check(mid)) r = mid;
        else l = mid+1;
    }
    ans = min(ans,l);
}

int main(){
    cin.tie(0),ios::sync_with_stdio(0);
    cin >> n >> m;
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= m;j++){
            cin >> a[i][j];
            mn = min(mn,a[i][j]);
        }
    }
    solve();
    for(int i = 1;i <= 3;i++){
        _rotate();
        solve();
    }
    cout << ans;
}

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