제출 #1319403

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

joioi

#include <bits/stdc++.h>

#define int long long 
#define pb push_back
using namespace std;

const int N=2010;
const int inf=1e18;
const int mod=1e9+7;

int n,m;

int a[N][N],b[N][N];

void rt() {
    for(int i=1;i<=m;i++) {
        for(int j=1;j<=n;j++) {
            b[i][j]=a[j][m-i+1];
        }
    }
    swap(n,m);
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            a[i][j]=b[i][j];
        }
    }
}

bool check(int x,int mn,int mx) {
    int r=inf;
    bool ok=1;
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            if(a[i][j]>mn+x) r=min(r,j);
        }
        for(int j=r;j<=m;j++) {
            if(a[i][j]<mx-x) ok=0;
        }
    }
    return ok;
}

signed main() {
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    int T=1;
    // cin>>T;
    while(T--) {
        //int n,m;
        cin>>n>>m;
        int mn=inf,mx=-inf;
        for(int i=1;i<=n;i++) {
            for(int j=1;j<=m;j++) {
                cin>>a[i][j];
                mx=max(mx,a[i][j]);
                mn=min(mn,a[i][j]);
            }
        }
        int ans=inf;
        for(int i=1;i<=4;i++) {
            rt();
            int l=0,r=inf,res;
            while(l<=r) {
                int mid=(l+r)/2;
                if(check(mid,mn,mx)) {
                    res=mid;
                    r=mid-1;
                }
                else l=mid+1;
            }
            ans=min(res,ans);
        }
        cout<<ans<<" ";
    }
}

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