제출 #1131398

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

joioi

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define int long long
#define ll long long
#define pb push_back
#define fi first
#define se second
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define ld long double
using namespace std;
typedef pair<int,int> pii;
typedef pair<char,char> pcc;
typedef pair<int,pii> ipii;
typedef pair<pii,pii> ipiii;
const int MAXN = 2010;
const int MAXA = 1e6;
const int MOD = 1e9+7;
const int INF = 1e18+10;
const int LOG = 21;
const ld EPS = 1e-12;
void chmx(int &a, int b){ a = max(a, b); }
void chmn(int &a, int b){ a = min(a, b); }

int n, m;
int a[MAXN][MAXN];
int MX;

bool cek(int x){
    int need = MX-x;

    int le = m, mn = INF, mx = 0;
    for(int i=1; i<=n; i++){
        int l = 0;
        for(int j=1; j<=m; j++){
            if(a[i][j] >= need) l = j;
            else break;
        }
        le = min(le, l);
        for(int j=le+1; j<=m; j++)
            mn = min(mn, a[i][j]), mx = max(mx, a[i][j]);
    }
    // cout << le << ' ' << mn << ' ' << mx << " mx\n";
    if(mx-mn <= x) return 1;

    le = m, mn = INF, mx = 0;
    for(int i=n; i>=1; i--){
        int l = 0;
        for(int j=1; j<=m; j++){
            if(a[i][j] >= need) l = j;
            else break;
        }
        le = min(le, l);
        for(int j=le+1; j<=m; j++)
            mn = min(mn, a[i][j]), mx = max(mx, a[i][j]);
    }
    // cout << le << ' ' << mn << ' ' << mx << " mx\n";
    if(mx-mn <= x) return 1;

    int ri = 1; mn = INF; mx = 0;
    for(int i=1; i<=n; i++){
        int r = m+1;
        for(int j=m; j>=1; j--){
            if(a[i][j] >= need) r = j;
            else break;
        }
        ri = max(ri, r);
        // cout << ri << ' ' <<  i << " i\n";
        for(int j=1; j<=ri-1; j++)
            mn = min(mn, a[i][j]), mx = max(mx, a[i][j]);
    }
    // cout << ri << ' ' << mn << ' ' << mx << " ri\n";
    if(mx-mn <= x) return 1;

    ri = 1; mn = INF; mx = 0;
    for(int i=n; i>=1; i--){
        int r = m+1;
        for(int j=m; j>=1; j--){
            if(a[i][j] >= need) r = j;
            else break;
        }
        ri = max(ri, r);
        // cout << ri << ' ' <<  i << " i\n";
        for(int j=1; j<=ri-1; j++)
            mn = min(mn, a[i][j]), mx = max(mx, a[i][j]);
    }
    // cout << ri << ' ' << mn << ' ' << mx << " ri\n";
    if(mx-mn <= x) return 1;

    return 0;
}
signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> m;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++) cin >> a[i][j], MX = max(MX, a[i][j]);

            // cout << cek(11) << '\n';
    int l=0, r=MX, mid=0, cnt=0;
    while(l<=r){
        mid = md;
        if(cek(mid)) cnt = mid, r = mid-1;
        else l = mid+1;
    }
    cout << cnt << '\n';
} 

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