Submission #1125220

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125220		njoop	The Kingdom of JOIOI (JOI17_joioi)	C++17	0 / 100	0 ms	320 KiB

joioi

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

int h, w, mn, mx, ans = 1e9+1;
vector<vector<int>> arr;

bool check(int val) {
    int mn2=1e9, mx2=0;
    vector<int> bound(h, w+1);
    for(int i=0; i<h; i++) {
        for(int j=0; j<w; j++) {
            if(arr[i][j] > mn+val) {
                bound[i] = min(bound[i], j);
            }
            if(bound[i] <= j) {
                mn2 = min(mn2, arr[i][j]);
                mx2 = max(mx2, arr[i][j]);
            }
        }
    }
    if(mx2-mn2 <= val) return true;
    return false;
}

int find() {
    int l=0, r=1e9;
    while(l < r) {
        int mid = l+(r-l)/2;
        if(check(mid)) {
            r = mid;
        } else {
            l = mid+1;
        }
    }
    return l;
}

signed main() {
    cin >> h >> w;
    arr.assign(h, vector<int>(w, 0));
    for(int i=0; i<h; i++) {
        for(int j=0; j<w; j++) {
            cin >> arr[i][j];
            if(i == 0 && j == 0) {
                mn = arr[i][j];
                mx = arr[i][j];
            }
            mn = min(mn, arr[i][j]);
            mx = max(mx, arr[i][j]);
        }
    }
    ans = min(ans, find());
    reverse(arr.begin(), arr.end());
    ans = min(ans, find());
    for(int i=0; i<h; i++) {
        reverse(arr[i].begin(), arr[i].end());
    }
    ans = min(ans, find());
    reverse(arr.begin(), arr.end());
    ans = min(ans, find());
    cout << ans;
    return 0;
}

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