제출 #1254921

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

joioi

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

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


#define fast_io     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define S           second
#define F           first
#define pb          push_back
#define for1(n)     for(int i=1;i<=n;i++)
#define for0(n)     for(int i=0;i<n;i++)
#define endl        '\n'
#define Mp          make_pair
#define all(x)      x.begin(),x.end()

const ll mod=1e9+7;
const ll inf=1e18+10;

const int N=2e3+10;
int A[N][N],B[N],C[N],D[N],n,m,q,k,dp[N],pre[N],L[N],R[N];
vector<int>g[N];
vector<pair<int,pii>>vec;

bool check(int x){
    for1(n){
        L[i]=0;R[i]=m+1;
    }
    for(pair<int,pii> p:vec){
        if(p.F>=vec.back().F-x)break;
        L[p.S.F]=max(L[p.S.F],p.S.S);
    }
    for(int i=vec.size()-1;i>=0;i--){
        pair<int,pii> p=vec[i];
        if(p.F<=vec[0].F+x)break;
        R[p.S.F]=min(R[p.S.F],p.S.S);
    }
    int mx=m;
    bool o=1;
    for1(n){
        mx=min(mx,R[i]-1);
        o&=(mx>=L[i]);
    }
    if(o)return 1;
    int mn=0;
    o=1;
    for1(n){
        mn=max(mn,L[i]+1);
        o&=(R[i]>=mn);
    }
    if(o)return 1;

    for1(n){
        L[i]=0;R[i]=m+1;
    }
    for(pair<int,pii> p:vec){
        if(p.F>=vec.back().F-x)break;
        R[p.S.F]=min(R[p.S.F],p.S.S);
    }
    for(int i=vec.size()-1;i>=0;i--){
        pair<int,pii> p=vec[i];
        if(p.F<=vec[0].F+x)break;
        L[p.S.F]=max(L[p.S.F],p.S.S);
    }
    mx=m;
    o=1;
    for1(n){
        mx=min(mx,R[i]-1);
        o&=(mx>=L[i]);
    }
    if(o)return 1;
    mn=0;
    o=1;
    for1(n){
        mn=max(mn,L[i]+1);
        o&=(R[i]>=mn);
    }
    if(o)return 1;
    return 0;
}
int main(){
    fast_io
    cin>>n>>m;
    for1(n)for(int j=1;j<=m;j++){cin>>A[i][j];vec.pb({A[i][j],{i,j}});}
    sort(all(vec));
    int l=-1,r=mod;
    while(r-l!=1){
        int mid=(l+r)>>1;
        if(check(mid)==0)l=mid;
        else r=mid;
    }
    cout<<l+1<<endl;
}

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