제출 #1277615

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

joioi

#include <bits/stdc++.h>
// Author: Kazuki_Will_Win_VOI_8703 
#define fi first
#define se second
#define pii pair<int, int>
#define ll long long
#define all(a) a.begin(), a.end()
using namespace std;

const int mn = 2e3 + 5, inf = 1e9;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

int h, w, a[mn][mn], b[mn][mn], min_val = inf;

void Megumi(){
    for(int i = 1; i <= h; i++){
        for(int j = 1; j <= w; j++){
            b[j][h - i + 1] = a[i][j];
        }
    }
    swap(w, h);
    for(int i = 1; i <= h; i++){
        for(int j = 1; j <= w; j++){
            a[i][j] = b[i][j];
        }
    }
}

bool check(int val){
    int mn = inf, mx = 0, lst = w;
    for(int i = 1; i <= h; i++){
        bool ok = true;
        for(int j = 1; j <= lst; j++){
            if(a[i][j] - min_val > val){
                lst = j - 1;
                break;
            }
        }
        for(int j = lst + 1; j <= w; j++){
            mn = min(mn, a[i][j]);
            mx = max(mx, a[i][j]);
        }
    }
    return (mx - mn <= val);
}

void solve(){
    cin >> h >> w;
    for(int i = 1; i <= h; i++){
        for(int j = 1; j <= w; j++){
            cin >> a[i][j];
            if(min_val > a[i][j]){
                min_val = a[i][j];
            }
        }
    }
    int ans = inf;
    for(int i = 1; i <= 4; i++){
        int l = 1, r = 1e9, cur = inf;
        while(l <= r){
            int mid = (l + r) >> 1;
            if(check(mid)){
                cur = mid;
                r = mid - 1;
            }
            else l = mid + 1;
        }
        ans = min(ans, cur);
        if(i < 4) Megumi();
    }
    cout << ans << '\n';
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t = 1;
    // cin >> t;
    while(t--) solve();
}

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