Submission #392066

#	Time	Username	Problem	Language	Result	Execution time	Memory
392066		palilo	The Kingdom of JOIOI (JOI17_joioi)	C++17	100 / 100	570 ms	54860 KiB

joioi

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

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
#ifdef home
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif
    int n, m;
    cin >> n >> m;

    vector<vector<int>> h(n, vector<int>(m));
    for (auto& v : h)
        for (auto& x : v)
            cin >> x;

    int mn_h = INT_MAX, mx_h = INT_MIN;
    for (const auto& v : h) {
        auto p = minmax_element(v.begin(), v.end());
        mn_h = min(mn_h, *p.first);
        mx_h = max(mx_h, *p.second);
    }

    auto ok = [&](int lim) {
        int64_t pivot = m;
        for (const auto& v : h) {
            pivot = min(pivot, find_if(v.begin(), v.begin() + pivot, [&](auto& x) { return x > mn_h + lim; }) - v.begin());
            if (any_of(v.begin() + pivot, v.end(), [&](auto& x) { return x < mx_h - lim; }))
                return false;
        }
        return true;
    };

    int ans = mx_h - mn_h;
    for (int t = 0; t < 4; ++t) {
        if (t & 1)
            for (auto& v : h)
                reverse(v.begin(), v.end());
        else if (t == 2)
            reverse(h.begin(), h.end());

        int lo = 0, hi = ans;
        while (lo != hi) {
            int mid = (lo + hi) >> 1;
            ok(mid) ? hi = mid : lo = mid + 1;
        }
        ans = min(ans, lo);
    }
    cout << ans;
}

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