oj.uz

Submission #129545

# Submission time Handle Problem Language Result Execution time Memory
129545 2019-07-12T13:26:06 Z trinhhung The Kingdom of JOIOI (JOI17_joioi) C++17
0 / 100
 50 ms 31864 KB 
#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;
}

signed 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.0

# Verdict Execution time Memory Grader output
1 Incorrect 50 ms 31864 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 50 ms 31864 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 50 ms 31864 KB Output isn't correct
2 Halted 0 ms 0 KB -