Submission #1176116

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176116		chikien2009	The Kingdom of JOIOI (JOI17_joioi)	C++20	100 / 100	246 ms	63288 KiB

joioi

#include <bits/stdc++.h>

using namespace std;

void setup()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int n, m, a, mina = 1e9, maxa = -1e9, l, r, mid, res;
pair<int, int> pre[2002][2002], suf[2002][2002];

inline bool Check(int inp)
{
    int upmax = m, upmin = m , downmax = m, downmin = m;
    bool v1 = true, v2 = true, v3 = true, v4 = true;
    for (int i = 1; i <= n; ++i)
    {
        while (0 < upmax && maxa - pre[i][upmax].first > inp)
        {
            upmax--;
        }
        while (0 < upmin && pre[i][upmin].second - mina > inp)
        {
            upmin--;
        }
        v1 &= (suf[i][upmax + 1].second - mina <= inp);
        v2 &= (maxa - suf[i][upmin + 1].first <= inp);
    }
    for (int i = n; i >= 1; --i)
    {
        while (0 < downmax && maxa - pre[i][downmax].first > inp)
        {
            downmax--;
        }
        while (0 < downmin && pre[i][downmin].second - mina > inp)
        {
            downmin--;
        }
        v3 &= (suf[i][downmax + 1].second - mina <= inp);
        v4 &= (maxa - suf[i][downmin + 1].first <= inp);
    }
    return v1 | v2 | v3 | v4;
}

int main()
{
    setup();

    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
    {
        pre[i][0] = pre[i][m + 1] = suf[i][0] = suf[i][m + 1] = {1e9, -1e9};
        for (int j = 1; j <= m; ++j)
        {
            cin >> a;
            mina = min(mina, a);
            maxa = max(maxa, a);
            pre[i][j] = suf[i][j] = {a, a};
            pre[i][j].first = min(pre[i][j].first, pre[i][j - 1].first);
            pre[i][j].second = max(pre[i][j].second, pre[i][j - 1].second);
        }
        for (int j = m; j >= 1; --j)
        {
            suf[i][j].first = min(suf[i][j].first, suf[i][j + 1].first);
            suf[i][j].second = max(suf[i][j].second, suf[i][j + 1].second);
        }
    }
    l = 0;
    r = 1e9;
    while (l <= r)
    {
        mid = (l + r) >> 1;
        if (Check(mid))
        {
            res = mid;
            r = mid - 1;
        }
        else
        {
            l = mid + 1;
        }
    }
    cout << res;
    return 0;
}

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