제출 #1291563

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1291563		trandangquang	The Kingdom of JOIOI (JOI17_joioi)	C++20	100 / 100	477 ms	24164 KiB

joioi

#include<bits/stdc++.h>
using namespace std;

#define foru(i,a,b) for(int i=(a); i<=(b); ++i)
#define ford(i,a,b) for(int i=(a); i>=(b); --i)
#define rep(i,a) for(int i=0; i<(a); ++i)
#define sz(a) (int)(a).size()
#define all(a) (a).begin(),(a).end()
#define bit(s,i) (((s)>>(i))&1)
#define ii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define ll long long
#define _ << " " <<

template <class X, class Y> bool maxi(X &x, Y y){return x<y?x=y,true:false;}
template <class X, class Y> bool mini(X &x, Y y){return x>y?x=y,true:false;}

const int N=2020;
const int INF=1e9;

int h,w,a[N][N],mi=INF,mx=0;
bool oka[N][N],okb[N][N];

bool chk(int diff){
    foru(i,1,h){
        foru(j,1,w){
            if(a[i][j]-mi<=diff) oka[i][j]=1;
            else oka[i][j]=0;

            if(mx-a[i][j]<=diff) okb[i][j]=1;
            else okb[i][j]=0;
        }
    }

    int lstI=0, lstD=w, l, r, cnt;
    foru(i,1,h){
        l=w+1, r=-1, cnt=0;
        foru(j,1,w) cnt+=okb[i][j];

        if(cnt==w) l=0, r=0;
        foru(j,1,w){
            cnt=cnt-okb[i][j]+oka[i][j];
            if(cnt==w) mini(l,j), maxi(r,j);
        }

        if(l==w+1){
            lstI=lstD=-1;
            break;
        }

        if(lstI!=-1){
            if(r<lstI){
                lstI=-1;
            } else if(l<=lstI){
                lstI=lstI;
            } else if(l>lstI){
                lstI=l;
            } else{
                assert(0);
            }
        }

        if(lstD!=-1){
            if(l>lstD){
                lstD=-1;
            } else if(r>=lstD){
                lstD=lstD;
            } else if(r<lstD){
                lstD=r;
            } else{
                assert(0);
            }
        }
    }
    if(lstI!=-1||lstD!=-1) return true;

    lstI=0, lstD=w;
    foru(i,1,h){
        l=w+1, r=-1, cnt=0;
        foru(j,1,w) cnt+=oka[i][j];

        if(cnt==w) l=0, r=0;
        foru(j,1,w){
            cnt=cnt-oka[i][j]+okb[i][j];
            if(cnt==w) mini(l,j), maxi(r,j);
        }

        if(l==w+1){
            lstI=lstD=-1;
            break;
        }

        if(lstI!=-1){
            if(r<lstI){
                lstI=-1;
            } else if(l<=lstI){
                lstI=lstI;
            } else if(l>lstI){
                lstI=l;
            } else{
                assert(0);
            }
        }

        if(lstD!=-1){
            if(l>lstD){
                lstD=-1;
            } else if(r>=lstD){
                lstD=lstD;
            } else if(r<lstD){
                lstD=r;
            } else{
                assert(0);
            }
        }
    }
    if(lstI!=-1||lstD!=-1) return true;

    return false;
}

void solve(){
    cin>>h>>w;
    foru(i,1,h) foru(j,1,w){
        cin>>a[i][j];
        mini(mi,a[i][j]);
        maxi(mx,a[i][j]);
    }

    int l=0,r=1e9,res=1e9;
    while(l<=r){
        int m=(l+r)>>1;
        if(chk(m)){
            r=m-1;
            res=m;
        }else{
            l=m+1;
        }
    }
    cout<<res<<'\n';
}

int32_t main(){
    #define task "test"
    if(fopen(task".inp","r")){
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);
    }
    cin.tie(0)->sync_with_stdio(0);

    int tc=1; //cin>>tc;
    rep(i,tc){
        solve();
    }
}

컴파일 시 표준 에러 (stderr) 메시지

joioi.cpp: In function 'int32_t main()':
joioi.cpp:149:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  149 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
joioi.cpp:150:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  150 |         freopen(task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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