제출 #1180247

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

joioi

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 1000000009
#define INF 1000000019
#define INFL 1000000000000000099LL

ll n,q,s,t,a,b,c,d,ans,k,m;
ll co[2007][2007],co2[2007][2007];
ll ile[2007][2];
ll mn=INFL,mx;

bool czyp(ll x){
 //  for(ll i=0;i<n;i++){
  //      for(ll j=0;j<m;j++)cout<<co[i][j]<<" ";
 //       cout<<"\n";
//    }
    ile[0][1]=INF;
    ile[0][0]=-1;
    for(ll i=0;i<n;i++){
        ll r=-1;
        ll l=INF;
        for(ll j=0;j<m;j++){
            if(co[i][j]-mn>x){
                r=max(r,j);
                
            }
            if(mx-co[i][j]>x){
                l=min(l,j);
            }
        }
    //    ile[i+1][0]=max(ile[i][0],r);
        ile[i+1][1]=min(ile[i][1],l);
        ile[i+1][0]=r;
   //     cout<<l<<" "<<r<<" "<<ile[i+1][1]<<" "<<ile[i+1][0]<<"\n";
       // if(ile[i+1][1]<=ile[i+1][0])return 0;
    }
    for(ll i=n-1;i>=0;i--){
        ile[i+1][1]=max(ile[i+1][1],ile[i+2][1]);
        if(ile[i+1][1]<=ile[i+1][0])return 0;
    }
    return 1;

}
void flipx(){
    for(ll i=0;i<n;i++){
        for(ll j=0;j<m/2;j++){
            swap(co[i][j],co[i][m-1-j]);
        }
            
    }
}
void flipy(){
    for(ll i=0;i<m;i++){
        for(ll j=0;j<n/2;j++){
            swap(co[j][i],co[n-1-j][i]);
        }
    }
}
bool czy(ll x){
   // cout<<"\n\n"<<x;
    if(czyp(x))return 1;
    flipx();
    if(czyp(x))return 1;
    flipy();
    if(czyp(x))return 1;
    flipx();
    if(czyp(x))return 1;
    flipx();
    //cout<<"xd";
    return 0;
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m;
    for(ll i=0;i<n;i++){
        for(ll j=0;j<m;j++){
            cin>>co[i][j];
            mn=min(mn,co[i][j]);
            mx=max(mx,co[i][j]);
        }
    }
    ll pocz=0;
    ll kon=1000000000;
    while(pocz!=kon){
        ll mid=(pocz+kon)/2;
        if(czy(mid))
            kon=mid;
        else
            pocz=mid+1;
    }
    cout<<pocz;
}

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