Submission #524040

#	Time	Username	Problem	Language	Result	Execution time	Memory
524040		Monarchuwu	The Kingdom of JOIOI (JOI17_joioi)	C++17	0 / 100	1 ms	460 KiB

joioi

#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];
int prf_ma[N][N], prf_mi[N][N];
int suf_ma[N][N], suf_mi[N][N];

int f[3][N];
bool check(int diff) {
    for (int i = 1; i <= h; ++i) {
        int lo(1), hi(w), m;
        while (lo <= hi) {
            m = (lo + hi) >> 1;
            if (prf_ma[i][m] - prf_mi[i][m] <= diff)
                lo = m + 1;
            else hi = m - 1;
        }
        f[0][i] = lo - 1;
    }

    f[1][0] = f[2][h + 1] = inf;
    for (int i = 1; i <= h; ++i) f[1][i] = min(f[0][i], f[1][i - 1]);
    for (int i = h; i >= 1; --i) f[2][i] = min(f[0][i], f[2][i + 1]);

    bool flag1(false), flag2(false);
    for (int i = 1; i <= h; ++i) {
        flag1 |= suf_ma[i][f[1][i] + 1] - suf_mi[i][f[1][i] + 1] > diff;
        flag2 |= suf_ma[i][f[2][i] + 1] - suf_mi[i][f[2][i] + 1] > diff;
    }
    return !flag1 || !flag2;
}

int main() {
    cin.tie(NULL)->sync_with_stdio(false);
    cin >> h >> w;
    for (int i = 1; i <= h; ++i) {
        prf_mi[i][0] = suf_mi[i][w + 1] = inf;
        for (int j = 1; j <= w; ++j) {
            cin >> a[i][j];
            prf_ma[i][j] = max(prf_ma[i][j - 1], a[i][j]);
            prf_mi[i][j] = min(prf_mi[i][j - 1], a[i][j]);
        }
        for (int j = w; j; --j) {
            suf_ma[i][j] = max(suf_ma[i][j + 1], a[i][j]);
            suf_mi[i][j] = min(suf_mi[i][j + 1], a[i][j]);
        }
    }

    int lo(0), hi(inf), m;
    while (lo <= hi) {
        m = (lo + hi) >> 1;
        if (check(m))
            hi = m - 1;
        else lo = m + 1;
    }
    cout << hi + 1 << '\n';
}
/**  /\_/\
 *  (= ._.)
 *  / >0  \>1
**/

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