Submission #1213878

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213878		Hamed_Ghaffari	The Kingdom of JOIOI (JOI17_joioi)	C++20	100 / 100	365 ms	16320 KiB

joioi

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

const int MXN = 2003;

int h, w, a[MXN][MXN];

inline bool check(int l1, int r1, int l2, int r2) {
    for(int tmp : {0, 1}) {
        for(int t : {0, 1}) {
            int lst = w;
            bool bad = 0;
            for(int i=(t?h:1); t?(i>=1):(i<=h); t?(i--):(i++)) {
                for(int j=1; j<=lst; j++)
                    if(!(l1 <= a[i][j] && a[i][j] <= r1)) {
                        lst = j-1;
                        break;
                    }
                for(int j=lst+1; j<=w; j++)
                    if(!(l2 <= a[i][j] && a[i][j] <= r2)) {
                        bad = 1;
                        break;
                    }
            }
            if(!bad) return 1;
        }
        swap(l1, l2); swap(r1, r2);
    }
    return 0;
}

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    cin >> h >> w;
    int mn = 1e9, mx = 0;
    for(int i=1; i<=h; i++)
        for(int j=1; j<=w; j++) {
            cin >> a[i][j];
            mn = min(mn, a[i][j]);
            mx = max(mx, a[i][j]);
        }
    int l=-1, r=mx-mn, mid;
    while(r-l>1) {
        mid = l+r>>1;
        (check(mn, mn+mid, mx-mid, mx) ? r : l) = mid;
    }
    cout << r << '\n';
    return 0;
}

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