Submission #734261

#	Time	Username	Problem	Language	Result	Execution time	Memory
734261		LucaIlie	The Kingdom of JOIOI (JOI17_joioi)	C++17	0 / 100	0 ms	340 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 ) {
    bool sePoate;

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

    sePoate = true;
    for ( int c = 0; c < m; c++ ) {
        int l = 0;
        while ( l < n && maxx - mat[l][c] <= x )
            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: 0 / 15
• Subtask 2: 0 / 45
• Subtask 3: 0 / 40