제출 #407126

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
407126		FEDIKUS	The Kingdom of JOIOI (JOI17_joioi)	C++17	0 / 100	1 ms	332 KiB

joioi

#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define xx first
#define yy second
#define srt(a) sort(a.begin(),a.end());
#define srtg(a,int) sort(a.begin(),a.end(),greater<int>())
#define lb(a,x) lower_bound(a.begin(),a.end(),x)
#define up(a,x) upper_bound(a.begin(),a.end(),x)
#define fnd(a,x) find(a.begin(),a.end(),x)
#define vstart auto startt=chrono::system_clock::now()
#define vend auto endd=chrono::system_clock::now()
#define vvreme chrono::duration<double> vremee=endd-startt
#define ios ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef string str;

const int maxn=2010;
int matra[maxn][maxn];

int h,w;
int vh=-1;
int vw=-1;
int mh=-1;
int mw=-1;
int maxi=INT_MIN;
int mini=INT_MAX;

bool obelezeno[maxn][maxn][2];

void obelezi(int x,int y,int v,int raz,int koji){
    if(x<0 || y<0 || x>=h || y>=w) return;
    //cout<<x<<" "<<y<<" "<<matra[x][y]<<" "<<v<<" "<<raz<<" "<<koji<<"\n";
    if(abs(matra[x][y]-v)>raz) return;
    if(obelezeno[x][y][koji]) return;
    obelezeno[x][y][koji]=1;
    obelezi(x+1,y,v,raz,koji);
    obelezi(x-1,y,v,raz,koji);
    obelezi(x,y+1,v,raz,koji);
    obelezi(x,y-1,v,raz,koji);
}

bool moze(int raz){
    for(int i=0;i<h;i++)
        for(int j=0;j<w;j++) obelezeno[i][j][0]=obelezeno[i][j][1]=false;
    obelezi(vh,vw,matra[vh][vw],raz,0);
    obelezi(mh,mw,matra[mh][mw],raz,1);
    //cout<<raz<<"\n";
    //for(int i=0;i<h;i++) {for(int j=0;j<w;j++) cout<<int(obelezeno[i][j][0])<<" "; cout<<"\n";} cout<<"\n";
    //for(int i=0;i<h;i++) {for(int j=0;j<w;j++) cout<<int(obelezeno[i][j][1])<<" "; cout<<"\n";} cout<<"\n\n";

    bool dh1=false;
    bool dv1=false;
    bool dh2=false;
    bool dv2=false;

    bool tren=true;
    for(int i=0;i<h;i++){
        int koji=0;
        for(int j=0;j<w;j++){
            if(obelezeno[i][j][koji]) continue;
            if(koji==1) tren=false;
            else koji=1;
            if(!obelezeno[i][j][koji]) tren=false;
        }
    }
    if(tren) dh1=true;
    tren=true;
    for(int i=0;i<h;i++){
        int koji=1;
        for(int j=0;j<w;j++){
            if(obelezeno[i][j][koji]) continue;
            if(koji==0) tren=false;
            else koji=0;
            if(!obelezeno[i][j][koji]) tren=false;
        }
    }
    if(tren) dh2=true;

    tren=true;
    for(int j=0;j<w;j++){
        int koji=0;
        for(int i=0;i<h;i++){
            if(obelezeno[i][j][koji]) continue;
            if(koji==1) tren=false;
            else koji=1;
            if(!obelezeno[i][j][koji]) tren=false;
        }
    }
    if(tren) dv1=true;
    tren=true;
    for(int j=0;j<w;j++){
        int koji=1;
        for(int i=0;i<h;i++){
            if(obelezeno[i][j][koji]) continue;
            if(koji==0) tren=false;
            else koji=0;
            if(!obelezeno[i][j][koji]) tren=false;
        }
    }
    if(tren) dv2=true;

    return (dh1 || dh2) && (dv1 || dv2);
}

void solve(){
    cin>>h>>w;
    for(int i=0;i<h;i++)
        for(int j=0;j<w;j++){
            cin>>matra[i][j];
            if(matra[i][j]>maxi){
                maxi=matra[i][j];
                vh=i;
                vw=j;
            }
            if(matra[i][j]<mini){
                mini=matra[i][j];
                mh=i;
                mw=j;
            }
        }
    int l=0;
    int r=1e9;
    int res=0;
    while(l<=r){
        int mid=l+(r-l)/2;
        if(moze(mid)){
            r=mid-1;
            res=mid;
        }else l=mid+1;
    }
    cout<<res;
}

int main(){
    ios;
    int t=1;
    //cin>>t;
    while(t--) solve();
    return 0;
}

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