Submission #129544

#	Time	Username	Problem	Language	Result	Execution time	Memory
129544		trinhhung	The Kingdom of JOIOI (JOI17_joioi)	C++14	0 / 100	38 ms	31940 KiB

joioi

#include<bits/stdc++.h>

using namespace std;

const int N = 2e3 + 5, INF = 1e9 + 7;
int n, m, Max, Min, ans;
int a[N][N], sum1[N][N], sum2[N][N];

bool check1 () {
    for (int prev = 0, i = 1; i <= n; ++i) {
        int next = -1;
        for (int j = prev; j <= m; ++j) {
            if (sum1[i][j] == j && sum2[i][m] - sum2[i][j] == m - j) { next = j; break ; }
        }
        if (next == -1) return false;
        prev = next;
    }
    return true;
}

bool check2 () {
    for (int prev = 0, i = 1; i <= n; ++i) {
        int next = -1;
        for (int j = prev; j <= m; ++j) {
            if (sum2[i][j] == j && sum1[i][m] - sum1[i][j] == m - j) { next = j; break ; }
        }
        if (next == -1) return false;
        prev = next;
    }
    return true;
}

bool check3 () {
    for (int prev = m, i = 1; i <= n; ++i) {
        int next = -1;
        for (int j = prev; j >= 0; --j) {
            if (sum1[i][j] == j && sum2[i][m] - sum2[i][j] == m - j) { next = j; break ; }
        }
        if (next == -1) return false;
        prev = next;
    }
    return true;
}

bool check4 () {
    for (int prev = m, i = 1; i <= n; ++i) {
        int next = -1;
        for (int j = prev; j >= 0; --j) {
            if (sum2[i][j] == j && sum1[i][m] - sum1[i][j] == m - j) { next = j; break ; }
        }
        if (next == -1) return false;
        prev = next;
    }
    return true;
}

int main () {
    Max = -INF, Min = INF;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> a[i][j];
            Min = min(Min, a[i][j]);
            Max = max(Max, a[i][j]);
        }
    }
    int l = 0, r = Max - Min;
    while (l < r) {
        int mid = (l + r) / 2;
        memset(sum1, 0, sizeof sum1);
        memset(sum2, 0, sizeof sum2);
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                sum1[i][j] = sum1[i][j - 1];
                sum2[i][j] = sum2[i][j - 1];
                if (a[i][j] - Min <= mid) ++ sum1[i][j];
                if (Max - a[i][j] <= mid) ++ sum2[i][j];
            }
        }
        if (check1() || check2() || check3() || check4() ) r = mid - 1, ans = mid;
        else l = mid + 1;
    }
    cout << ans;
}

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