제출 #737735

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
737735		1075508020060209tc	The Kingdom of JOIOI (JOI17_joioi)	C++14	100 / 100	1642 ms	133584 KiB

joioi

#include<bits/stdc++.h>
using namespace std;
//#define int long long
int n;int m;
int TPV;int BTV;
int gr[2010][2010];
int tgr[2010][2010];
int psmx[2010][2010];
int psmn[2010][2010];
int sfmx[2010][2010];
int sfmn[2010][2010];


int ans;

int chmx(int id,int l,int r){
if(l==1){
    return psmx[id][r];
}
    return sfmx[id][l];

}
int chmn(int id,int l,int r){
if(l==1){
    return psmn[id][r];
}
    return sfmn[id][l];
}



void spin(){

for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        tgr[j][n-i+1 ]=gr[i][j];
    }
}
swap(n,m);
for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        gr[i][j]=tgr[i][j];
    }
}
}

void precalc(){

for(int i=1;i<=n;i++){
    psmn[i][1]=gr[i][1];
    psmx[i][1]=gr[i][1];
    for(int j=2;j<=m;j++){
        psmn[i][j]=min(psmn[i][j-1],gr[i][j]);
        psmx[i][j]=max(psmx[i][j-1],gr[i][j]);
    }
    sfmn[i][m]=gr[i][m];
    sfmx[i][m]=gr[i][m];
    for(int j=m-1;j>=1;j--){
        sfmn[i][j]=min(sfmn[i][j+1],gr[i][j]);
        sfmx[i][j]=max(sfmx[i][j+1],gr[i][j]);
    }
}


}

int ok1(int mid){
int lst=m;
int tp=TPV-mid;
int bt=BTV+mid;
for(int i=1;i<=n;i++){
    int l=0;int r=lst;
    while(l<r){
        int mi=l+(r-l+1)/2;
        if((mi==0||(mi!=0&&chmn(i,1,mi)>=tp)) ){
            l=mi;
        }else{
            r=mi-1;
        }
    }
    lst=l;
    if((lst!=m&&chmx(i,lst+1,m)>bt) ){return 0;}
}
return 1;
}

int ok2(int mid){
int lst=m;
int tp=TPV-mid;
int bt=BTV+mid;
for(int i=1;i<=n;i++){
    int l=0;int r=lst;
    while(l<r){
        int mi=l+(r-l+1)/2;
        if((mi==0||(mi!=0&&chmx(i,1,mi)<=bt)) ){
            l=mi;
        }else{
            r=mi-1;
        }
    }
    lst=l;
    if((lst!=m&&chmn(i,lst+1,m)<tp) ){return 0;}
}
return 1;
}




int solve(){
int l=0;int r=1e9;

while(l<r){
    int mi=l+(r-l)/2;
    if((ok1(mi)||ok2(mi))){
        r=mi;
    }else{
        l=mi+1;
    }
}
return l;
}



signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        cin>>gr[i][j];
    }
}
TPV=gr[1][1];BTV=gr[1][1];
for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        TPV=max(TPV,gr[i][j]);
        BTV=min(BTV,gr[i][j]);
    }
}
ans=1e9;
precalc();
ans=solve();
for(int t=1;t<=3;t++){
    spin();
    precalc();
    ans=min(ans,solve());
}
cout<<ans<<endl;





}

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