Submission #127204

#	Time	Username	Problem	Language	Result	Execution time	Memory
127204		EntityIT	The Kingdom of JOIOI (JOI17_joioi)	C++14	100 / 100	1395 ms	86384 KiB

joioi

#include<bits/stdc++.h>

using namespace std;

const int N = (int)2e3 + 5, M = N, inf = (int)1e9 + 123;
int n, m, a[N][M], mnA = inf, mxA = -inf, sumMn[N][M], sumMx[N][M];

bool check1 () {
    for (int prv = 0, i = 1; i <= n; ++i) {
        int nxt = -1;
        for (int j = prv; j <= m; ++j) {
            if (sumMn[i][j] == j && sumMx[i][m] - sumMx[i][j] == m - j) { nxt = j; break ; }
        }
        if (nxt == -1) return false;
        prv = nxt;
    }
    return true;
}

bool check2 () {
    for (int prv = 0, i = 1; i <= n; ++i) {
        int nxt = -1;
        for (int j = prv; j <= m; ++j) {
            if (sumMx[i][j] == j && sumMn[i][m] - sumMn[i][j] == m - j) { nxt = j; break ; }
        }
        if (nxt == -1) return false;
        prv = nxt;
    }
    return true;
}

bool check3 () {
    for (int prv = m, i = 1; i <= n; ++i) {
        int nxt = -1;
        for (int j = prv; j >= 0; --j) {
            if (sumMn[i][j] == j && sumMx[i][m] - sumMx[i][j] == m - j) { nxt = j; break ; }
        }
        if (nxt == -1) return false;
        prv = nxt;
    }
    return true;
}

bool check4 () {
    for (int prv = m, i = 1; i <= n; ++i) {
        int nxt = -1;
        for (int j = prv; j >= 0; --j) {
            if (sumMx[i][j] == j && sumMn[i][m] - sumMn[i][j] == m - j) { nxt = j; break ; }
        }
        if (nxt == -1) return false;
        prv = nxt;
    }
    return true;
}

int 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];
            mnA = min(mnA, a[i][j]);
            mxA = max(mxA, a[i][j]);
        }
    }

    int lAns = 0, rAns = mxA - mnA;
    while (lAns < rAns) {
        int mid = (lAns + rAns) >> 1;
        memset(sumMn, 0, sizeof sumMn);
        memset(sumMx, 0, sizeof sumMx);
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                sumMn[i][j] = sumMn[i][j - 1];
                sumMx[i][j] = sumMx[i][j - 1];
                if (a[i][j] - mnA <= mid) ++sumMn[i][j];
                if (mxA - a[i][j] <= mid) ++sumMx[i][j];
            }
        }
        if (check1() || check2() || check3() || check4() ) rAns = mid;
        else lAns = mid + 1;
    }

    cout << lAns;

    return 0;
}

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