Submission #939458

#	Time	Username	Problem	Language	Result	Execution time	Memory
939458		kitlix	The Kingdom of JOIOI (JOI17_joioi)	C++17	0 / 100	1 ms	348 KiB

joioi

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int INF = 30;

signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    int n, m;
    cin >> n >> m;
    vector<vector<int>> a(n, vector<int>(m));
    int mn = INF;
    for (auto& r : a)
        for (auto& el : r) {
            cin >> el;
            mn = min(mn, el);
        }
    auto check = [&](int dif) {
        int othermx = -INF, othermn = INF;
        int curmx = m;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < curmx; ++j) {
                if (a[i][j] - mn > dif) {
                    curmx = j;
                    break;
                }
            }
            for (int j = curmx; j < m; ++j) {
                othermx = max(othermx, a[i][j]);
                othermn = min(othermn, a[i][j]);
            }
        }
        if (othermx - othermn <= dif || curmx == m)
            return true;
        othermx = -INF, othermn = INF;
        curmx = m;
        for (int i = n - 1; i >= 0; --i) {
            for (int j = 0; j < curmx; ++j) {
                if (a[i][j] - mn > dif) {
                    curmx = j;
                    break;
                }
            }
            for (int j = curmx; j < m; ++j) {
                othermx = max(othermx, a[i][j]);
                othermn = min(othermn, a[i][j]);
            }
        }
        if (othermx - othermn <= dif || curmx == m)
            return true;
        othermx = -INF, othermn = INF;
        curmx = -1;
        for (int i = 0; i < n; ++i) {
            for (int j = m - 1; j > curmx; --j) {
                if (a[i][j] - mn > dif) {
                    curmx = j;
                    break;
                }
            }
            for (int j = curmx; j >= 0; --j) {
                othermx = max(othermx, a[i][j]);
                othermn = min(othermn, a[i][j]);
            }
        }
        if (othermx - othermn <= dif || curmx == -1)
            return true;
        othermx = -INF, othermn = INF;
        curmx = -1;
        for (int i = n - 1; i >= 0; --i) {
            for (int j = m - 1; j > curmx; --j) {
                if (a[i][j] - mn > dif) {
                    curmx = j;
                    break;
                }
            }
            for (int j = curmx; j >= 0; --j) {
                othermx = max(othermx, a[i][j]);
                othermn = min(othermn, a[i][j]);
            }
        }
        if (othermx - othermn <= dif || curmx == -1)
            return true;
        return false;
        };
    int l = 0, r = INF;
    while (l + 1 < r) {
        int mid = (l + r) / 2;
        if (check(mid))
            r = mid;
        else
            l = mid;
    }
    cout << r;
}

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