제출 #734282

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
734282		LucaIlie	The Kingdom of JOIOI (JOI17_joioi)	C++17	60 / 100	4016 ms	54796 KiB

joioi

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 2000 + 1;
int n, m, minn = 2e9, maxx = 0;
int mat[MAX_N][MAX_N], lin[MAX_N];

bool check( int x ) {
    int last;
    bool sePoate;

    sePoate = true;
    last = n;
    for ( int c = 0; c < m; c++ ) {
        int l = 0;
        while ( l < last && mat[l][c] - minn <= x )
            l++;
        last = l;
        for ( ; l < n; l++ ) {
            if ( maxx - mat[l][c] > x )
                sePoate = false;
        }
    }
    if ( sePoate )
        return true;

    sePoate = true;
    last = n;
    for ( int c = m - 1; c >= 0; c-- ) {
        int l = 0;
        while ( l < last && mat[l][c] - minn <= x )
            l++;
        last = l;
        for ( ; l < n; l++ ) {
            if ( maxx - mat[l][c] > x )
                sePoate = false;
        }
    }
    if ( sePoate )
        return true;

    last = n;
    sePoate = true;
    for ( int c = 0; c < m; c++ ) {
        int l = 0;
        while ( l < last && maxx - mat[l][c] <= x )
            l++;
        last = l;
        for ( ; l < n; l++ ) {
            if ( mat[l][c] - minn > x )
                sePoate = false;
        }
    }
    if ( sePoate )
        return true;

    last = n;
    sePoate = true;
    for ( int c = m - 1; c >= 0; c-- ) {
        int l = 0;
        while ( l < last && maxx - mat[l][c] <= x )
            l++;
        last = l;
        for ( ; l < n; l++ ) {
            if ( mat[l][c] - minn > x )
                sePoate = false;
        }
    }
    if ( sePoate )
        return true;

    return false;

}

int main() {
    cin >> n >> m;
    for ( int l = 0; l < n; l++ ) {
        for ( int c = 0; c < m; c++ ) {
            cin >> mat[l][c];
            minn = min( minn, mat[l][c] );
            maxx = max( maxx, mat[l][c] );
        }
    }

    int l = -1, r = maxx - minn;
    while ( r - l > 1 ) {
        int mid = (l + r) / 2;
        if ( check( mid ) )
            r = mid;
        else
            l = mid;
    }

    cout << r;

    return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 45 / 45
• Subtask 3: 0 / 40