Submission #140530

#	Time	Username	Problem	Language	Result	Execution time	Memory
140530		meatrow	The Kingdom of JOIOI (JOI17_joioi)	C++17	100 / 100	1183 ms	54924 KiB

joioi

//#pragma GCC optimize("O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native")
//#pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;

const int N = 2000;

int a[N][N];
int bot[N];
int b[N];
int mx;

int solve(int h, int w) {
    for (int i = 0; i < h; i++) {
        b[i] = -1;
        for (int j = 0; j < w; j++) {
            if (a[i][j] == mx) {
                b[i] = j;
            }
        }
    }
    int l = -1, r = 1e9;
    while (l + 1 < r) {
        int mid = (l + r) / 2;
        for (int i = 0; i < h; i++) {
            bot[i] = w;
            for (int j = 0; j < w; j++) {
                if (a[i][j] + mid < mx) {
                    bot[i] = j;
                    break;
                }
            }
        }
        //decreasing
        int d = w - 1;
        bool f = true;
        int kek1 = mx;
        int kek2 = 0;
        for (int i = 0; i < h; i++) {
            d = min(d, bot[i] - 1);
            if (d < b[i]) {
                f = false;
                break;
            }
            for (int j = d + 1; j < w; j++) {
                kek1 = min(kek1, a[i][j]);
                kek2 = max(kek2, a[i][j]);
            }
        }
        if (f && kek2 - kek1 <= mid) {
            r = mid;
            continue;
        }
        l = mid;
    }
    return r;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int h, w;
    cin >> h >> w;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            cin >> a[i][j];
            mx = max(mx, a[i][j]);
        }
    }
    int ans = solve(h, w);
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w / 2; j++) {
            swap(a[i][j], a[i][w - j - 1]);
        }
    }
    ans = min(ans, solve(h, w));
    for (int j = 0; j < w; j++) {
        for (int i = 0; i < h / 2; i++) {
            swap(a[i][j], a[h - i - 1][j]);
        }
    }
    ans = min(ans, solve(h, w));
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w / 2; j++) {
            swap(a[i][j], a[i][w - j - 1]);
        }
    }
    ans = min(ans, solve(h, w));
    cout << ans;
    return 0;
}

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