제출 #1308202

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1308202		_nothing_	The Kingdom of JOIOI (JOI17_joioi)	C++17	100 / 100	2612 ms	47900 KiB

joioi

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

int numRow, numCol;

#define MAX_N 2020
int a[MAX_N][MAX_N], minCol[MAX_N][MAX_N];
int tmp[MAX_N + 2][MAX_N + 2];

void rotate90() {
    swap(numRow, numCol);

    for (int i = 1; i <= numRow; ++i)
        for (int j = 1; j <= numCol; ++j)
            tmp[i][j] = a[j][i];

    for (int i = 1; i <= numRow; ++i)
        for (int j = 1; j <= numCol; ++j)
            a[i][j] = tmp[i][j];
}

void flip180() {
    for (int j = 1; j <= numCol; ++j) {
        int l = 1, r = numRow;
        while (l <= r) swap(a[l++][j], a[r--][j]);
    }
}

bool getResults(int rangeAdd) {
    int minVal = (int) 1e9 + 7, maxVal = 0;

    for (int i = 1; i <= numRow; ++i)
        for (int j = 1; j <= numCol; ++j) {
            minVal = min(minVal, a[i][j]);
            maxVal = max(maxVal, a[i][j]);
        }

    if (maxVal - minVal <= rangeAdd) return true;

    /// min from bot;

    for (int j = 1; j <= numCol; ++j) minCol[numRow + 1][j] = 1e9 + 7;

    for (int i = numRow; i >= 1; --i) {
        for (int j = 1; j <= numCol; ++j) {
            minCol[i][j] = min(minCol[i + 1][j], a[i][j]);
        }
    }

    /// inc from left to right;
    int last = 1e9, minOther = 1e9 + 7;
    for (int j = numCol; j >= 1; --j) {
        int high = 0;
        for (int i = 1; i <= numRow; ++i) {
            if (a[i][j] <= minVal + rangeAdd) {
                ++high;
            } else break;
        }

        last = min(last, high);

        minOther = min(minOther, minCol[last + 1][j]);
    }

    if (maxVal - minOther <= rangeAdd) return true;

    /// inc from right downto left;
    last = 1e9, minOther = 1e9 + 7;
    for (int j = 1; j <= numCol; ++j) {
        int high = 0;
        for (int i = 1; i <= numRow; ++i) {
            if (a[i][j] <= minVal + rangeAdd) {
                ++high;
            } else break;
        }

        last = min(last, high);

        minOther = min(minOther, minCol[last + 1][j]);
    }

    if (maxVal - minOther <= rangeAdd) return true;

    return false;
}

bool check(int val) {
    for (int step = 1; step <= 4; ++step) {
        if (step % 2 == 0) flip180();
        else rotate90();

        if (getResults(val)) return true;
    }
    return false;
}

int main() {
    ios_base::sync_with_stdio(false);cin.tie(nullptr);
    cin >> numRow >> numCol;
    for (int i = 1; i <= numRow; ++i)
        for (int j = 1; j <= numCol; ++j) cin >> a[i][j];

    int l = 0, r = (int) 1e9, g, vt = -1;
    while (l <= r) {
        g = (l + r) >> 1;
        if (check(g)) vt = g, r = g - 1;
        else l = g + 1;
    }

    assert(vt != -1);

    cout << vt;

    return 0;
}

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