Submission #1131298

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131298		v2v2	The Kingdom of JOIOI (JOI17_joioi)	C++17	0 / 100	0 ms	324 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) {
    // minimum on left, maximum on right
    // left decreases
    int mx_col = w;
    bool good = true;
    for (int row = 1; row <= h && good; row++) {
        int col;
        for (col = 0; col < mx_col; col++) {
            if (a[row][col+1] > mini + diff) break;
        }
        mx_col = col;
        int mn = 1e9;
        for (col = col + 1; col <= w; col++) {
            mn = min(mn, a[row][col]);
        }
        if (mn < maxi - diff) good = false;
    }
    if (good) return true;

    // right decreases
    int mn_col = 0;
    good = true;
    for (int row = 1; row <= h && good; row++) {
        int col;
        for (col = w+1; col > mn_col; col--) {
            if (a[row][col-1] < maxi - diff) break;
        }
        mn_col = col;
        int mx = 0;
        for (col = col - 1; col > 0; col--) {
            mx = max(mx, a[row][col]);
        }
        if (mx > mini + diff) good = false;
    }
    if (good) return true;

    // maximum on left, minimum on right
    // left decreases
    mx_col = w;
    good = true;
    for (int row = 1; row <= h && good; row++) {
        int col;
        for (col = 0; col < mx_col; col++) {
            if (a[row][col+1] < maxi - diff) break;
        }
        mx_col = col;
        int mx = 0;
        for (col = col + 1; col <= w; col++) {
            mx = max(mx, a[row][col]);
        }
        if (mx > mini + diff) good = false;
    }
    if (good) return true;

    // right decreases
    mn_col = 0;
    good = true;
    for (int row = 1; row <= h && good; row++) {
        int col;
        for (col = w+1; col > mn_col; col--) {
            if (a[row][col-1] > mini + diff) break;
        }
        mn_col = col;
        int mn = 0;
        for (col = col - 1; col > 0; col--) {
            mn = min(mn, a[row][col]);
        }
        if (mn < maxi - diff) 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: 0 / 15
• Subtask 2: 0 / 45
• Subtask 3: 0 / 40