Submission #1125228

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

joioi

#include <bits/stdc++.h>
using namespace std;
#define int long long
int h, w, mn, mx, ans = 1e9+1;
vector<vector<int>> arr;

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

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

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