제출 #113652

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
113652		popovicirobert	The Kingdom of JOIOI (JOI17_joioi)	C++14	15 / 100	14 ms	2304 KiB

joioi

#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++) {
        if(i % 2 == 0) {
            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: 15 / 15
• Subtask 2: 0 / 45
• Subtask 3: 0 / 40