제출 #755532

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
755532		PixelCat	The Kingdom of JOIOI (JOI17_joioi)	C++14	100 / 100	989 ms	102372 KiB

joioi

#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
#define int LL
#define INF (int)(1e18)
using namespace std;
using LL = long long;
using pii = pair<int, int>;

const int MAXN = 2010;

int a[MAXN][MAXN];
int tmp[MAXN][MAXN];
int r[MAXN];
int l[MAXN];

// rotate CCW once
void rot(int &n, int &m) {
    For(i, 0, n - 1) For(j, 0, m - 1) {
        tmp[m - j - 1][i] = a[i][j];
    }
    swap(n, m);
    For(i, 0, n - 1) For(j, 0, m - 1) {
        a[i][j] = tmp[i][j];
    }
}

void check1(int n, int m, int lo) {
    For(i, 0, n - 1) {
        r[i] = -1;
        for(; r[i] + 1 < m && a[i][r[i] + 1] >= lo; r[i]++);
        if(i) r[i] = min(r[i], r[i - 1]);
    }
}

void check2(int n, int m, int hi) {
    Forr(i, n - 1, 0) {
        l[i] = m;
        for(; l[i] - 1 >= 0 && a[i][l[i] - 1] <= hi; l[i]--);
        if(i < n - 1) l[i] = max(l[i], l[i + 1]);
    }
}

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    // =^-w-^=
    int n, m; cin >> n >> m;
    int mx = -1, mn = INF;
    For(i, 0, n - 1) For(j, 0, m - 1) {
        cin >> a[i][j];
        mx = max(mx, a[i][j]);
        mn = min(mn, a[i][j]);
    }

    int ans = INF;
    For(_, 0, 3) {
        int hi = mx - mn;
        int lo = -1;
        while(hi - lo > 1) {
            int mi = (hi + lo) / 2;
            check1(n, m, mx - mi);
            check2(n, m, mn + mi);
            bool ok = true;
            For(i, 0, n - 1) {
                if(r[i] + 1 < l[i]) {
                    ok = false;
                    break;
                }
            }
            if(ok) hi = mi;
            else lo = mi;
        }
        ans = min(ans, hi);
        rot(n, m);
    }
    cout << ans << "\n";
    return 0;
}

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