Submission #1181077

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181077		anteknne	The Kingdom of JOIOI (JOI17_joioi)	C++20	100 / 100	671 ms	35668 KiB

joioi

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;

#define pb push_back
#define pii pair<int, int>
#define pll pair<ll, ll>
#define st first
#define nd second
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define debug false

const int MAXW = 2000;
const ll MAXA = INT_MAX;
ll a[MAXW][MAXW];
ll a2[MAXW][MAXW];
bool jest[MAXW][MAXW];
ll maks, minn;
int w, h;

bool ok (ll d) {
    for (int i = 0; i < w; i ++) {
        for (int j = 0; j < h; j ++) {
            jest[i][j] = false;
        }
    }

    int poprzedni = h - 1;
    bool rosnie = true;
    for (int i = 0; i < w; i ++) {
        int r = -1;

        for (int j = 0; j <= poprzedni; j ++) {
            if (a[i][j] - minn <= d) {
                r = j;
                jest[i][j] = true;
            } else {
                break;
            }
        }
        poprzedni = r;

    }

    if (poprzedni == h - 1) {
        return true;
    }

    ll aktmin = LLONG_MAX, aktmaks = 0;
    for (int i = 0; i < w; i ++) {
        for (int j = 0; j < h; j ++) {
            if (!jest[i][j]) {
                aktmin = min(aktmin, a[i][j]);
                aktmaks = max(aktmaks, a[i][j]);
            }
        }
    }

    if (aktmaks - aktmin <= d) {
        return true;
    }


    return false;
}

void obroc () {
    for (int i = 0; i < h; i ++) {
        for (int j = 0; j < w; j ++) {
            a2[i][j] = a[j][i];
        }
    }

    swap(w, h);
    swap(a2, a);

    for (int i = 0; i < w; i ++) {
        for (int j = 0; j < h; j ++) {
            cout << a[i][j] << " ";
        }
        cout << "\n";
    }
    cout << "\n";
}

ll licz () {
    ll pocz = 0, kon = MAXA, wyn = 0;

    while (pocz <= kon) {
        ll sr  = (pocz + kon)/ 2;
        if (ok(sr)) {
            wyn = sr;
            kon = sr - 1LL;
        } else {
            pocz = sr + 1LL;
        }
    }

    return wyn;
}

int main () {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> w >> h;

    for (int i = 0; i < w; i ++) {
        for (int j = 0; j < h; j ++) {
            cin >> a[i][j];
        }
    }

    maks = a[0][0];
    minn = a[0][0];

    for (int i = 0; i < w; i ++) {
        for (int j = 0; j < h; j ++) {
            maks = max(maks, a[i][j]);
            minn = min(minn, a[i][j]);
        }
    }

    ll rek = licz();

    for (int i = 0; i < w; i ++) {
        reverse(a[i], a[i] + h);
    }

    rek = min(rek, licz());

    reverse(a, a + w);

    rek = min(rek, licz());


    for (int i = 0; i < w; i ++) {
        reverse(a[i], a[i] + h);
    }

    rek = min(rek, licz());

    cout << rek << "\n";



    return 0;
}

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