oj.uz

Submission #734255

# Submission time Handle Problem Language Result Execution time Memory
734255 2023-05-02T07:33:40 Z LucaIlie The Kingdom of JOIOI (JOI17_joioi) C++17
0 / 100
 1 ms 468 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 2000 + 1;
int mat[MAX_N][MAX_N], minPref[MAX_N][MAX_N], maxPref[MAX_N][MAX_N], minSuf[MAX_N][MAX_N], maxSuf[MAX_N][MAX_N], lin[MAX_N];

int main() {
    int n, m, minn = 2e9, lm = 0, cm = 0;

    cin >> n >> m;
    for ( int l = 0; l < n; l++ ) {
        for ( int c = 0; c < m; c++ ) {
            cin >> mat[l][c];
            if ( mat[l][c] < minn ) {
                minn = mat[l][c];
                lm = l;
                cm = c;
            }
        }
    }

    for ( int c = 0; c < m; c++ ) {
        minPref[c][0] = maxPref[c][0] = mat[0][c];
        for ( int l = 1; l < n; l++ ) {
            minPref[c][l] = min( minPref[c][l - 1], mat[l][c] );
            maxPref[c][l] = max( maxPref[c][l - 1], mat[l][c] );
        }
        minSuf[c][n] = 2e9;
        minSuf[c][n - 1] = maxSuf[c][n - 1] = mat[n - 1][c];
        for ( int l = n - 2; l >= 0; l-- ) {
            minSuf[c][l] = min( minSuf[c][l + 1], mat[l][c] );
            maxSuf[c][l] = max( maxSuf[c][l + 1], mat[l][c] );
        }
    }

    int l = -1, r = 1e9;
    while ( r - l > 1 ) {
        int mid = (l + r) / 2;

        bool sePoate1 = true;
        for ( int c = 0; c < m; c++ ) {
            int maxx = 0;
            lin[c] = 0;
            maxx = max( maxx, mat[lin[c]][c] );
            while ( lin[c] < n && maxx - minn <= mid ) {
                lin[c]++;
                maxx = max( maxx, mat[lin[c]][c] );
            }
        }
        int left = 1;
        while ( left < m && lin[left] == lin[left - 1] )
            left++;
        int right = m - 2;
        while ( right >= 0 && lin[right] == lin[right + 1] )
            right--;
        for ( int c = left; c <= right; c++ ) {
            if ( lin[c] == 0 )
                sePoate1 = false;
            if ( lin[c] == n )
                lin[c]--;
        }
        if ( lin[cm] <= lm )
            sePoate1 = false;
        int minVal = 2e9, maxVal = 0;
        for ( int c = 0; c < m; c++ ) {
            minVal = min( minVal, minSuf[c][lin[c]] );
            maxVal = max( maxVal, maxSuf[c][lin[c]] );
        }
        if ( maxVal - minVal > mid )
            sePoate1 = false;

        bool sePoate2 = true;
        for ( int c = 0; c < m; c++ ) {
            int maxx = 0;
            lin[c] = n;
            while ( lin[c] > 0 && maxx - minn <= mid ) {
                lin[c]--;
                maxx = max( maxx, mat[lin[c]][c] );
            }
        }
        left = 1;
        while ( left < m && lin[left] == lin[left - 1] )
            left++;
        right = m - 2;
        while ( right >= 0 && lin[right] == lin[right + 1] )
            right--;
        for ( int c = left; c <= right; c++ ) {
            if ( lin[c] == 0 )
                sePoate2 = false;
            if ( lin[c] == n )
                lin[c]--;
        }
        if ( lin[cm] >= lm )
            sePoate2 = false;
        minVal = 2e9, maxVal = 0;
        for ( int c = 0; c < m; c++ ) {
            minVal = min( minVal, minPref[c][lin[c]] );
            maxVal = max( maxVal, maxPref[c][lin[c]] );
        }
        if ( maxVal - minVal > mid )
            sePoate2 = false;

        if ( sePoate1 | sePoate2 )
            r = mid;
        else
            l = mid;
    }

    cout << r;

    return 0;
}

Subtask #1
0 / 15.0

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

Subtask #2
0 / 45.0

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

Subtask #3
0 / 40.0

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