Submission #96181

#	Time	Username	Problem	Language	Result	Execution time	Memory
96181		fedoseevtimofey	The Kingdom of JOIOI (JOI17_joioi)	C++14	100 / 100	1642 ms	55124 KiB

joioi

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
 
vector <vector <int>> a;
 
const int Inf = 1e9;
 
int mx = -Inf;
int mn = Inf;
 
int n, m;
 
void rev1() {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m / 2; ++j) {
            swap(a[i][j], a[i][m - j - 1]);
        }
    }
}
 
void rev2() {
    for (int i = 0; i < n / 2; ++i) {
        for (int j = 0; j < m; ++j) {
            swap(a[i][j], a[n - i - 1][j]);
        }
    }
}
 
int ans = Inf;
 
void bins() {
    int l = -1, r = Inf;
    while (r - l > 1) {
        int mid = (l + r) >> 1;
        int cr = m;
        bool fl = true;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (abs(mx - a[i][j]) > mid) cr = min(cr, j);
            }
            for (int j = cr; j < m; ++j) {
                if (abs(mn - a[i][j]) > mid) {
                    fl = false;
                }
            }
        }
        if (fl) r = mid;
        else l = mid;
    }
    ans = min(ans, r);
}
 
int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.setf(ios::fixed); cout.precision(20);
    #ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    cin >> n >> m;
    a.resize(n, vector <int> (m));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> a[i][j];
            mx = max(mx, a[i][j]);
            mn = min(mn, a[i][j]);
        }
    }
    ans = mx - mn;
    bins();
    rev1();
    bins();
    rev2();
    bins();
    rev1();
    bins();
    cout << ans << '\n';
}

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