oj.uz

Submission #113651

# Submission time Handle Problem Language Result Execution time Memory
113651 2019-05-27T11:17:50 Z popovicirobert The Kingdom of JOIOI (JOI17_joioi) C++14
0 / 100
 2 ms 384 KB 
#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
// 217
// 44

using namespace std;

const int INF = 1e9;
const int MAXN = 2000;

int mat[MAXN + 1][MAXN + 1], aux[MAXN + 1][MAXN + 1];
int n, m, mn, mx;

inline void rot() {

    int i, j;

    for(i = 1; i <= m; i++) {
        for(j = 1; j <= n; j++) {
            aux[i][j] = mat[n - j + 1][i];
        }
    }

    swap(n, m);
    for(i = 1; i <= n; i++) {
        for(j = 1; j <= m; j++) {
            mat[i][j] = aux[i][j];
        }
    }
}


inline bool solve(int dif) {

    int l = INF, r = -INF;
    int last = m;

    for(int j = 1; j <= m; j++) {
        int i = 1;
        while(i <= min(n, last) && mat[i][j] <= mn + dif) {
            i++;
        }

        last = min(last, i - 1);

        while(i <= n) {
            l = min(l, mat[i][j]);
            r = max(r, mat[i][j]);

            i++;
        }
    }

    if(r - l <= dif) {
        return 1;
    }

    last = 1;

    l = INF, r = -INF;

    for(int j = 1; j <= m; j++) {
        int i = n;
        while(i >= max(1, last) && mat[i][j] <= mn + dif) {
            i--;
        }

        last = max(last, i + 1);

        while(i >= 1) {
            l = min(l, mat[i][j]);
            r = max(r, mat[i][j]);

            if(r - l > dif) {
                return 0;
            }

            i--;
        }
    }

    return r - l <= dif;

}


inline bool check(int dif) {

    bool ans = 0;
    for(int i = 0; i < 4 && ans == 0; i += 2) {
        ans |= solve(dif);
        rot();
    }

    return ans;

}


int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.out");
    int i, j;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> m;

    mx = -INF, mn = INF;

    for(i = 1; i <= n; i++) {
        for(j = 1; j <= m; j++) {
            cin >> mat[i][j];
            mn = min(mn, mat[i][j]);
            mx = max(mx, mat[i][j]);
        }
    }

    int res = -1;

    for(int step = 1 << 29; step; step >>= 1) {
        if(res + step <= mx - mn && check(res + step) == 0) {
            res += step;
        }
    }

    cout << res + 1;

    //cin.close();
    //cout.close();
    return 0;
}

Subtask #1
0 / 15.0

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

Subtask #2
0 / 45.0

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

Subtask #3
0 / 40.0

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