Submission #524084

#	Time	Username	Problem	Language	Result	Execution time	Memory
524084		Monarchuwu	The Kingdom of JOIOI (JOI17_joioi)	C++17	100 / 100	470 ms	54888 KiB

joioi

// JOI chứa min, IOI chứa max
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;

const int N = 2000 + 3, inf = 1e9 + 7;
int h, w;
int a[N][N], mi = inf, ma;

bool check1(int diff) { // trái trên
    for (int i = 1, p(w); i <= h; ++i) {
        for (int j = p; j; --j)
            if (a[i][j] - mi > diff) p = min(p, j - 1); // [1..p] [p+1..w]
        for (int j = p + 1; j <= w; ++j)
            if (ma - a[i][j] > diff) return false;
    }
    return true;
}

bool check2(int diff) { // trái dưới
    for (int i = h, p(w); i; --i) {
        for (int j = p; j; --j)
            if (a[i][j] - mi > diff) p = min(p, j - 1); // [1..p] [p+1..w]
        for (int j = p + 1; j <= w; ++j)
            if (ma - a[i][j] > diff) return false;
    }
    return true;
}

bool check3(int diff) { // phải trên
    for (int i = 1, p(w); i <= h; ++i) {
        for (int j = p; j; --j)
            if (ma - a[i][j] > diff) p = min(p, j - 1); // [1..p] [p+1..w]
        for (int j = p + 1; j <= w; ++j)
            if (a[i][j] - mi > diff) return false;
    }
    return true;
}

bool check4(int diff) { // phải dưới
    for (int i = h, p(w); i; --i) {
        for (int j = p; j; --j)
            if (ma - a[i][j] > diff) p = min(p, j - 1); // [1..p] [p+1..w]
        for (int j = p + 1; j <= w; ++j)
            if (a[i][j] - mi > diff) return false;
    }
    return true;
}

int main() {
    cin.tie(NULL)->sync_with_stdio(false);
    cin >> h >> w;
    for (int i = 1; i <= h; ++i)
        for (int j = 1; j <= w; ++j) {
            cin >> a[i][j];
            mi = min(mi, a[i][j]);
            ma = max(ma, a[i][j]);
        }

    int lo(0), hi(ma - mi - 1), m;
    while (lo <= hi) {
        m = (lo + hi) >> 1;
        if (check1(m) || check2(m) || check3(m) || check4(m))
            hi = m - 1;
        else lo = m + 1;
    }
    cout << hi + 1 << '\n';
}
/**  /\_/\
 *  (= ._.)
 *  / >0  \>1
**/

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