Submission #1131300

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131300		v2v2	The Kingdom of JOIOI (JOI17_joioi)	C++17	100 / 100	510 ms	32020 KiB

joioi

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define all(x) x.begin(), x.end()
#define fastio ios::sync_with_stdio(0); cin.tie(0)
#define mp make_pair

#define int ll

const int MAXN = 2e3 + 5;

int a[MAXN][MAXN];
int h, w;

int mini, maxi;

bool check(int diff) {
    vector<int> left_has_mx(h+1), left_has_mn(h+1), right_has_mx(h+1), right_has_mn(h+1);

    for (int i = 1; i <= h; i++) {
        int l = 0;
        while (l < w && a[i][l + 1] <= mini + diff) l++;
        left_has_mn[i] = l;
        l = 0;
        while (l < w && a[i][l + 1] >= maxi - diff) l++;
        left_has_mx[i] = l;
        int r = w+1;
        while (r > 1 && a[i][r - 1] <= mini + diff) r--;
        right_has_mn[i] = r;
        r = w+1;
        while (r > 1 && a[i][r - 1] >= maxi - diff) r--;
        right_has_mx[i] = r;
    }

    // left has max, decreasing l
    bool good = true;
    int mx_l = w;
    for (int i = 1; i <= h && good; i++) {
        mx_l = min(mx_l, left_has_mx[i]);
        int r = max(mx_l + 1, right_has_mn[i]);
        if (r > mx_l + 1) good = false;
    }
    if (good) return true;

    // left has min, decreasing l
    good = true;
    mx_l = w;
    for (int i = 1; i <= h && good; i++) {
        mx_l = min(mx_l, left_has_mn[i]);
        int r = max(mx_l + 1, right_has_mx[i]);
        if (r > mx_l + 1) good = false;
    }
    if (good) return true;

    // left has max, increasing r
    good = true;
    int mn_r = 1;
    for (int i = 1; i <= h && good; i++) {
        mn_r = max(mn_r, right_has_mn[i]);
        int l = min(mn_r - 1, left_has_mx[i]);
        if (l < mn_r - 1) good = false;
    }
    if (good) return true;

    // left has max, increasing r
    good = true;
    mn_r = 1;
    for (int i = 1; i <= h && good; i++) {
        mn_r = max(mn_r, right_has_mx[i]);
        int l = min(mn_r - 1, left_has_mn[i]);
        if (l < mn_r - 1) good = false;
    }
    return good;
}

signed main() {
    fastio;
    cin >> h >> w;

    mini = 1e9, maxi = 0;
    for (int i = 1; i <= h; i++) for (int j = 1; j <= w; j++) {
        cin >> a[i][j];
        mini = min(mini, a[i][j]);
        maxi = max(maxi, a[i][j]);
    }

    int l = 0, r = 1e9;

    while (l < r) {
        int mid = (l + r) / 2;

        if (check(mid)) r = mid;
        else l = mid + 1;
    }

    cout << l << endl;
}

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