oj.uz

Submission #96180

# Submission time Handle Problem Language Result Execution time Memory
96180 2019-02-06T18:05:24 Z fedoseevtimofey The Kingdom of JOIOI (JOI17_joioi) C++14
0 / 100
 2 ms 376 KB 
#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 (mid + a[i][j] < mx) cr = min(cr, j);
            }
            for (int j = cr; j < m; ++j) {
                if (mn + mid < a[i][j]) {
                    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();
    cout << ans << '\n';
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -