Submission #1125232

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

joioi

#include <bits/stdc++.h>

using namespace std;

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

bool check(int val) {
    int mn2=1e9+1, mx2=0, bound=w+1;
    for(int i=0; i<h; i++) {
        for(int j=0; j<w; j++) {
            if(arr[i][j] > mn+val) {
                bound = min(bound, j);
            }
            if(j >= bound) {
                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 < 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];
        }
    }
    mn = arr[0][0];
    for(int i=0; i<h; i++) {
        for(int j=0; j<w; j++) {
            mn = min(mn, 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: 15 / 15
• Subtask 2: 45 / 45
• Subtask 3: 40 / 40