oj.uz

Submission #734261

# Submission time Handle Problem Language Result Execution time Memory
734261 2023-05-02T07:53:49 Z LucaIlie The Kingdom of JOIOI (JOI17_joioi) C++17
0 / 100
 0 ms 340 KB 
#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.0

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

Subtask #2
0 / 45.0

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

Subtask #3
0 / 40.0

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