제출 #1019315

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1019315		Arteezy	The Kingdom of JOIOI (JOI17_joioi)	C++17	0 / 100	1 ms	348 KiB

joioi

#include <bits/stdc++.h>
#define Aiko ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define pb push_back
using namespace std;
const int INF = 1e9;

signed main() {
    int h, w, i, j;
    cin >> h >> w;
    vector<vector<int>> a(h, vector<int>(w));
    int mx = 0, mn = INF;
    for (i = 0; i < h; i++) {
        for (j = 0; j < w; j++) {
            cin >> a[i][j];
            mn = min(mn, a[i][j]);
            mx = max(mx, a[i][j]);
        }
    }
    vector<vector<int>> color(h, vector<int>(w));
    auto fun = [&](int t) {
        for (i = 0; i < h; i++) {
            for (j = 0; j < w; j++) {
                if (abs(a[i][j] - mn) <= t) color[i][j] = 1;
            }
        }
        for (i = 0; i < h; i++) {
            for (j = 0; j < w; j++) {
                if (color[i][j] != 1 && abs(a[i][j] - mx) <= t) color[i][j] = 2;
                else if (abs(a[i][j] - mx) <= t) color[i][j] = 3;
            }
        }
        vector<int> ans(h), ans1(h), ans2(w), ans3(w);
        for (i = 0; i < h; i++) {
            bool a2 = 0;
            for (j = 0; j < w; j++) {
                if (color[i][j] == 1) ans[i] = j;
                if (color[i][j] == 2 && a2 == 0) {
                    a2 = 1;
                    ans1[i] = j;
                }
            }
        }
        for (i = 0; i < h; i++) {
            bool a2 = 0;
            for (j = 0; j < h; j++) {
                if (color[i][j] == 1) ans[i] = j;
                if (color[i][j] == 2 && a2 == 0) {
                    a2 = 1;
                    ans1[i] = j;
                }
            }
        }
        for (i = 0; i < w; i++) {
            bool a2 = 0;
            for (j = 0; j < h; j++) {
                if (color[i][j] == 1) ans2[i] = j;
                if (color[i][j] == 2 && a2 == 0) {
                    a2 = 1;
                    ans3[i] = j;
                }
            }
        }
        bool a1 = 0;
        for (i = 0; i < h; i++) {
            if (ans[i] > ans1[i]) a1 = 1;
        }
        for (i = 0; i < w; i++) {
            if (ans2[i] > ans3[i]) a1 = 1;
        }
        if (a1 == 1) return false;
        else return true;
    };
    int l = 0, r = 1e9 + 7;
    while (r > l + 1) {
        int m = (l + r) >> 1;
        if (fun(m)) r = m;
        else l = m;
    }
    if (fun(r)) cout << r;
    else cout << l;

}

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