제출 #1131295

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1131295		v2v2	The Kingdom of JOIOI (JOI17_joioi)	C++17	0 / 100	0 ms	320 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;

bool check_p(int diff) {
    int mx_col = w;
    for (int row = 1; row <= h; row++) {
        int mn = a[row][1], mx = a[row][1];
        int col;
        for (col = 1; col < mx_col; col++) {
            if (max(mx, a[row][col+1]) - min(mn, a[row][col+1]) > diff) break;
            mn = min(mn, a[row][col+1]);
            mx = max(mx, a[row][col+1]);
        }
        mx_col = col;
        mn = 1e9; mx = 0;
        for (col = col + 1; col <= w; col++) {
            mn = min(mn, a[row][col]);
            mx = max(mx, a[row][col]);
        }
        if (mx - mn > diff) return false;
    }
    return true;
}

bool check_n(int diff) {
    int mn_col = 1;
    for (int row = 1; row <= h; row++) {
        int mn = a[row][w], mx = a[row][w];
        int col;
        for (col = w; col > mn_col; col--) {
            if (max(mx, a[row][col-1]) - min(mn, a[row][col-1]) > diff) break;
            mn = min(mn, a[row][col-1]);
            mx = max(mx, a[row][col-1]);
        }
        mn_col = col;
        mn = 1e9; mx = 0;
        for (col = col - 1; col >= 1; col--) {
            mn = min(mn, a[row][col]);
            mx = max(mx, a[row][col]);
        }
        if (mx - mn > diff) return false;
    }
    return true;
}

bool check(int diff) {
    return check_p(diff) || check_n(diff);
}

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

    for (int i = 1; i <= h; i++) for (int j = 1; j <= w; j++) cin >> 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