Submission #226684

#	Time	Username	Problem	Language	Result	Execution time	Memory
226684		DS007	The Kingdom of JOIOI (JOI17_joioi)	C++14	100 / 100	1589 ms	58884 KiB

joioi

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int H = 2000;
int a[H][H];
int h, w, mi, ma;

void pre() {
    mi = 1e18, ma = -1;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++)
            mi = min(mi, a[i][j]), ma = max(ma, a[i][j]);
    }
}

bool check(int dif) {
    int ll = mi + dif + 1, ul = ma - dif - 1;
    bool track[h][w] = {};

    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            if (a[i][j] >= ll)
                track[i][j] = true;
        }
    }

    for (int i = 0; i < h; i++) {
        int li = w, hi = -1;
        for (int j = 0; j < w; j++) {
            if (track[i][j])
                li = min(li, j), hi = max(hi, j);
        }

        for (int j = li; j <= hi; j++) {
            if (a[i][j] <= ul)
                return false;
            track[i][j] = true;
        }
    }

    for (int j = 0; j < w; j++) {
        int li = h, hi = -1;
        for (int i = 0; i < h; i++) {
            if (track[i][j])
                li = min(li, i), hi = max(hi, i);
        }

        for (int i = li; i <= hi; i++) {
            if (a[i][j] <= ul)
                return false;
            track[i][j] = true;
        }
    }

    bool check = true;
    for (int i = h - 1, max_ind = -1; i >= 0; i--) {
        for (int j = 0; j < w; j++) {
            if (track[i][j])
                max_ind = max(max_ind, j);
        }
        for (int j = 0; j <= max_ind; j++) {
            if (a[i][j] <= ul)
                check = false;
        }
    }

    if (check)
        return true;
    check = true;

    for (int i = 0, max_ind = -1; i < h; i++) {
        for (int j = 0; j < w; j++) {
            if (track[i][j])
                max_ind = max(max_ind, j);
        }
        for (int j = 0; j <= max_ind; j++) {
            if (a[i][j] <= ul)
                check = false;
        }
    }

    if (check)
        return true;
    check = true;

    for (int i = h - 1, min_ind = w; i >= 0; i--) {
        for (int j = 0; j < w; j++) {
            if (track[i][j])
                min_ind = min(min_ind, j);
        }
        for (int j = w - 1; j >= min_ind; j--) {
            if (a[i][j] <= ul)
                check = false;
        }
    }

    if (check)
        return true;
    check = true;

    for (int i = 0, min_ind = w; i < h; i++) {
        for (int j = 0; j < w; j++) {
            if (track[i][j])
                min_ind = min(min_ind, j);
        }
        for (int j = w - 1; j >= min_ind; j--) {
            if (a[i][j] <= ul)
                check = false;
        }
    }

    if (check)
        return true;
    return false;
}

void solveTestCase() {
    cin >> h >> w;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++)
            cin >> a[i][j];
    }
    pre();

    int lo = 0, hi = 1e9, ans = 1e9;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (check(mid))
            ans = mid, hi = mid - 1;
        else
            lo = mid + 1;
    }

    cout << ans;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int test = 1;
    // cin >> test;
    for (int i = 1; i <= test; i++)
        solveTestCase();
}

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