oj.uz

Submission #524078

# Submission time Handle Problem Language Result Execution time Memory
524078 2022-02-08T15:25:44 Z Monarchuwu The Kingdom of JOIOI (JOI17_joioi) C++17
0 / 100
 1 ms 328 KB 
// JOI chứa min, IOI chứa max
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;

const int N = 2000 + 3, inf = 1e9 + 7;
int h, w;
int a[N][N], mi = inf, ma;

bool check1(int diff) { // p[1] >= p[2] >= ... >= p[h]
    for (int i = 1, p(w); i <= h; ++i) {
        for (int j = w; j; --j)
            if (a[i][j] - mi > diff) p = min(p, j - 1); // [1..p] [p+1..w]
        for (int j = p + 1; j <= w; ++j)
            if (ma - a[i][j] > diff) return false;
    }
    return true;
}

bool check2(int diff) { // p[1] <= p[2] <= ... <= p[h]
    for (int i = h, p(w); i; --i) {
        for (int j = w; j; --j)
            if (a[i][j] - mi > diff) p = min(p, j - 1); // [1..p] [p+1..w]
        for (int j = p + 1; j <= w; ++j)
            if (ma - a[i][j] > diff) return false;
    }
    return true;
}

int main() {
    cin.tie(NULL)->sync_with_stdio(false);
    cin >> h >> w;
    for (int i = 1; i <= h; ++i)
        for (int j = 1; j <= w; ++j) {
            cin >> a[i][j];
            mi = min(mi, a[i][j]);
            ma = max(ma, a[i][j]);
        }

    int lo(0), hi(ma - mi - 1), m;
    while (lo <= hi) {
        m = (lo + hi) >> 1;
        if (check1(m) || check2(m))
            hi = m - 1;
        else lo = m + 1;
    }
    cout << hi + 1 << '\n';
}
/**  /\_/\
 *  (= ._.)
 *  / >0  \>1
**/

Subtask #1
0 / 15.0

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

Subtask #2
0 / 45.0

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

Subtask #3
0 / 40.0

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