oj.uz

Submission #837177

# Submission time Handle Problem Language Result Execution time Memory
837177 2023-08-25T07:05:16 Z _martynas The Kingdom of JOIOI (JOI17_joioi) C++11
0 / 100
 1 ms 340 KB 
#include <bits/stdc++.h>

using namespace std;

const int mxn = 2005;
const int inf = 2e9;

int h, w;
int mxa = 0;
int a[mxn][mxn];
bool b[mxn][mxn];

int check() {
    int mnj = h;
    int mn = inf/2, mx = 0;
    for(int i = 0; i < h; i++) {
        for(int j = 0; j < mnj; j++) {
            if(b[i][j]) mnj = j;
        }
        for(int j = mnj; j < w; j++) {
            mn = min(mn, a[i][j]);
            mx = max(mx, a[i][j]);
        }
    }
    return mx-mn;
}

bool solve(int k) {
    for(int i = 0; i < h; i++)
    for(int j = 0; j < w; j++)
        b[i][j] = mxa-a[i][j]>k;
    bool ok = false;
    // check
    ok = ok || (check() <= k);
    // reverse rows
    for(int i = 0; i < h; i++) for(int j = 0; j < w/2; j++) swap(a[i][j], a[i][w-j-1]);
    for(int i = 0; i < h; i++) for(int j = 0; j < w/2; j++) swap(b[i][j], b[i][w-j-1]);
    // check
    ok = ok || (check() <= k);
    // reverse cols
    for(int i = 0; i < h/2; i++) for(int j = 0; j < w; j++) swap(a[i][j], a[h-i-1][j]);
    for(int i = 0; i < h/2; i++) for(int j = 0; j < w; j++) swap(b[i][j], b[h-i-1][j]);
    // check
    ok = ok || (check() <= k);
    // reverse rows
    for(int i = 0; i < h; i++) for(int j = 0; j < w/2; j++) swap(a[i][j], a[i][w-j-1]);
    for(int i = 0; i < h; i++) for(int j = 0; j < w/2; j++) swap(b[i][j], b[i][w-j-1]);
    // check
    ok = ok || (check() <= k);
    // reverse cols
    for(int i = 0; i < h/2; i++) for(int j = 0; j < w; j++) swap(a[i][j], a[h-i-1][j]);
    for(int i = 0; i < h/2; i++) for(int j = 0; j < w; j++) swap(b[i][j], b[h-i-1][j]);
    return ok;
}

int main(int argc, char const *argv[]) {
    cin >> h >> w;
    for(int i = 0; i < h; i++) {
        for(int j = 0; j < w; j++) {
            cin >> a[i][j]; mxa = max(mxa, a[i][j]);
        }
    }
    int lo = 0, hi = inf/2;
    while(lo < hi) {
        int m = (lo+hi)/2;
        cerr << lo << " " << hi << "\n";
        if(solve(m)) {
            hi = m;
        }
        else {
            lo = m+1;
        }
    }
    cout << lo << "\n";
    return 0;
}

Subtask #1
0 / 15.0

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

Subtask #2
0 / 45.0

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

Subtask #3
0 / 40.0

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