oj.uz

답안 #129547

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
129547 2019-07-12T13:27:20 Z trinhhung The Kingdom of JOIOI (JOI17_joioi) C++17
0 / 100
 39 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 () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    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;
    return 0;
}

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 39 ms 31864 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 39 ms 31864 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 39 ms 31864 KB Output isn't correct
2 Halted 0 ms 0 KB -