제출 #837426

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
837426		unnick	The Kingdom of JOIOI (JOI17_joioi)	C++14	100 / 100	2765 ms	22140 KiB

joioi

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> alts;
vector<bool> arr;
int w,h;

bool valid(int lb, int ub, bool dx, bool dy) {
    for (int y = 0; y < h; y++) {
        for (int x = 0; x < w; x++) {
            // if (alts[x+y*w] > lb && alts[x+y*w] < ub) return false;
            arr[x+y*w] = (alts[x+y*w] > ub);
        }
    }
    for (int y = dy?h-1:0; y < h && y >= 0; y += dy?-1:1) {
        for (int x = dx?w-1:0; x < w && x >= 0; x += dx?-1:1) {
            bool tmp = arr[x+y*w];
            if (dx?x<w-1:x>0) tmp = tmp || arr[x+(dx?1:-1)+y*w];
            if (dy?y<h-1:y>0) tmp = tmp || arr[x+(y+(dy?1:-1))*w];
            if (tmp && alts[x+y*w] < lb) return false;
            arr[x+y*w] = tmp;
        }
    }
    return true;
}

int main() {
    cin >> h >> w;
    int la = 2000000000, ha = 0;
    for (int y = 0; y < h; y++) {
        for (int x = 0; x < w; x++) {
            int tmp;
            cin >> tmp;
            alts.push_back(tmp);
            la = min(la, tmp);
            ha = max(ha, tmp);
        }
    }
    arr.resize(w*h);
    int l = 0, h = ha-la;
    while (l+1<h) {
        int m = (l+h)/2;
        bool b = valid(ha-m, la+m, false, false) || valid(ha-m, la+m, true, false) || valid(ha-m, la+m, false, true) || valid(ha-m, la+m, true, true);
        if (b) {
            h = m;
        } else {
            l = m;
        }
    }
    cout << h << "\n";
}

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