oj.uz

Submission #939458

# Submission time Handle Problem Language Result Execution time Memory
939458 2024-03-06T11:37:24 Z kitlix The Kingdom of JOIOI (JOI17_joioi) C++17
0 / 100
 1 ms 348 KB 
#include <bits/stdc++.h>
#define int long long

using namespace std;

const int INF = 30;

signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    int n, m;
    cin >> n >> m;
    vector<vector<int>> a(n, vector<int>(m));
    int mn = INF;
    for (auto& r : a)
        for (auto& el : r) {
            cin >> el;
            mn = min(mn, el);
        }
    auto check = [&](int dif) {
        int othermx = -INF, othermn = INF;
        int curmx = m;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < curmx; ++j) {
                if (a[i][j] - mn > dif) {
                    curmx = j;
                    break;
                }
            }
            for (int j = curmx; j < m; ++j) {
                othermx = max(othermx, a[i][j]);
                othermn = min(othermn, a[i][j]);
            }
        }
        if (othermx - othermn <= dif || curmx == m)
            return true;
        othermx = -INF, othermn = INF;
        curmx = m;
        for (int i = n - 1; i >= 0; --i) {
            for (int j = 0; j < curmx; ++j) {
                if (a[i][j] - mn > dif) {
                    curmx = j;
                    break;
                }
            }
            for (int j = curmx; j < m; ++j) {
                othermx = max(othermx, a[i][j]);
                othermn = min(othermn, a[i][j]);
            }
        }
        if (othermx - othermn <= dif || curmx == m)
            return true;
        othermx = -INF, othermn = INF;
        curmx = -1;
        for (int i = 0; i < n; ++i) {
            for (int j = m - 1; j > curmx; --j) {
                if (a[i][j] - mn > dif) {
                    curmx = j;
                    break;
                }
            }
            for (int j = curmx; j >= 0; --j) {
                othermx = max(othermx, a[i][j]);
                othermn = min(othermn, a[i][j]);
            }
        }
        if (othermx - othermn <= dif || curmx == -1)
            return true;
        othermx = -INF, othermn = INF;
        curmx = -1;
        for (int i = n - 1; i >= 0; --i) {
            for (int j = m - 1; j > curmx; --j) {
                if (a[i][j] - mn > dif) {
                    curmx = j;
                    break;
                }
            }
            for (int j = curmx; j >= 0; --j) {
                othermx = max(othermx, a[i][j]);
                othermn = min(othermn, a[i][j]);
            }
        }
        if (othermx - othermn <= dif || curmx == -1)
            return true;
        return false;
        };
    int l = 0, r = INF;
    while (l + 1 < r) {
        int mid = (l + r) / 2;
        if (check(mid))
            r = mid;
        else
            l = mid;
    }
    cout << r;
}

Subtask #1
0 / 15.0

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

Subtask #2
0 / 45.0

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

Subtask #3
0 / 40.0

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