Submission #837177

#	Time	Username	Problem	Language	Result	Execution time	Memory
837177		_martynas	The Kingdom of JOIOI (JOI17_joioi)	C++11	0 / 100	1 ms	340 KiB

joioi

#include <bits/stdc++.h>

using namespace std;

const int mxn = 2005;
const int inf = 2e9;

int h, w;
int mxa = 0;
int a[mxn][mxn];
bool b[mxn][mxn];

int check() {
    int mnj = h;
    int mn = inf/2, mx = 0;
    for(int i = 0; i < h; i++) {
        for(int j = 0; j < mnj; j++) {
            if(b[i][j]) mnj = j;
        }
        for(int j = mnj; j < w; j++) {
            mn = min(mn, a[i][j]);
            mx = max(mx, a[i][j]);
        }
    }
    return mx-mn;
}

bool solve(int k) {
    for(int i = 0; i < h; i++)
    for(int j = 0; j < w; j++)
        b[i][j] = mxa-a[i][j]>k;
    bool ok = false;
    // check
    ok = ok || (check() <= k);
    // reverse rows
    for(int i = 0; i < h; i++) for(int j = 0; j < w/2; j++) swap(a[i][j], a[i][w-j-1]);
    for(int i = 0; i < h; i++) for(int j = 0; j < w/2; j++) swap(b[i][j], b[i][w-j-1]);
    // check
    ok = ok || (check() <= k);
    // reverse cols
    for(int i = 0; i < h/2; i++) for(int j = 0; j < w; j++) swap(a[i][j], a[h-i-1][j]);
    for(int i = 0; i < h/2; i++) for(int j = 0; j < w; j++) swap(b[i][j], b[h-i-1][j]);
    // check
    ok = ok || (check() <= k);
    // reverse rows
    for(int i = 0; i < h; i++) for(int j = 0; j < w/2; j++) swap(a[i][j], a[i][w-j-1]);
    for(int i = 0; i < h; i++) for(int j = 0; j < w/2; j++) swap(b[i][j], b[i][w-j-1]);
    // check
    ok = ok || (check() <= k);
    // reverse cols
    for(int i = 0; i < h/2; i++) for(int j = 0; j < w; j++) swap(a[i][j], a[h-i-1][j]);
    for(int i = 0; i < h/2; i++) for(int j = 0; j < w; j++) swap(b[i][j], b[h-i-1][j]);
    return ok;
}

int main(int argc, char const *argv[]) {
    cin >> h >> w;
    for(int i = 0; i < h; i++) {
        for(int j = 0; j < w; j++) {
            cin >> a[i][j]; mxa = max(mxa, a[i][j]);
        }
    }
    int lo = 0, hi = inf/2;
    while(lo < hi) {
        int m = (lo+hi)/2;
        cerr << lo << " " << hi << "\n";
        if(solve(m)) {
            hi = m;
        }
        else {
            lo = m+1;
        }
    }
    cout << lo << "\n";
    return 0;
}

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