oj.uz

Submission #1066184

# Submission time Handle Problem Language Result Execution time Memory
1066184 2024-08-19T16:10:07 Z sammyuri The Kingdom of JOIOI (JOI17_joioi) C++17
100 / 100
 3764 ms 106008 KB 
#include <bits/stdc++.h>
using namespace std;


int height[4][2005][2005];
bool taken[2005][2005];
int biggest = 0;
int h, w;
bool check(int limit, int index) {
    // take all cells that are big enough
    int req = biggest - limit;
    int curbig = 0, cursmall = 1e9;
    for (int i = 0; i < h; i ++)
        for (int j = 0; j < w; j ++)
            if (height[index][i][j] < req)
                taken[i][j] = true;
            else
                taken[i][j] = false;
    // turn into one component
    for (int i = 0; i < h; i ++) {
        bool seen = false;
        for (int j = w - 1; j >= 0; j --) {
            if (taken[i][j]) seen = true;
            if (seen) {
                taken[i][j] = true;
                curbig = max(curbig, height[index][i][j]);
                cursmall = min(cursmall, height[index][i][j]);
            }
        }
    }
    for (int j = 0; j < w; j ++) {
        bool seen = false;
        for (int i = h - 1; i >= 0; i --) {
            if (taken[i][j]) seen = true;
            if (seen) {
                taken[i][j] = true;
                curbig = max(curbig, height[index][i][j]);
                cursmall = min(cursmall, height[index][i][j]);
            }
        }
    }
    return (curbig - cursmall) <= limit;
}
bool possible(int limit) {
    if (check(limit, 0))
        return true;
    if (check(limit, 1))
        return true;
    if (check(limit, 2))
        return true;
    if (check(limit, 3))
        return true;
    return false;
}


int main() {
    cin >> h >> w;
    for (int i = 0; i < h; i ++) {
        for (int j = 0; j < w; j ++)    
            cin >> height[0][i][j], biggest = max(biggest, height[0][i][j]);
    }
    for (int i = 0; i < h; i ++)
        for (int j = 0; j < w; j ++)
            height[1][i][j] = height[0][h - i - 1][j],
            height[2][i][j] = height[0][i][w - j - 1],
            height[3][i][j] = height[0][h - i - 1][w - j - 1];
    int L = 0, R = 1e9 + 5;
    while (L != R) {
        int mid = (L + R) / 2;
        if (possible(mid))
            R = mid;
        else
            L = mid + 1;
    }
    cout << L << endl;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 0 ms 604 KB Output is correct
9 Correct 1 ms 600 KB Output is correct
10 Correct 0 ms 604 KB Output is correct
11 Correct 0 ms 604 KB Output is correct
12 Correct 0 ms 604 KB Output is correct
13 Correct 0 ms 604 KB Output is correct
14 Correct 1 ms 604 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 0 ms 604 KB Output is correct
9 Correct 1 ms 600 KB Output is correct
10 Correct 0 ms 604 KB Output is correct
11 Correct 0 ms 604 KB Output is correct
12 Correct 0 ms 604 KB Output is correct
13 Correct 0 ms 604 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 9 ms 4492 KB Output is correct
17 Correct 16 ms 4696 KB Output is correct
18 Correct 16 ms 4932 KB Output is correct
19 Correct 24 ms 4920 KB Output is correct
20 Correct 18 ms 4344 KB Output is correct
21 Correct 26 ms 5052 KB Output is correct
22 Correct 28 ms 5012 KB Output is correct
23 Correct 26 ms 4956 KB Output is correct
24 Correct 23 ms 4292 KB Output is correct
25 Correct 27 ms 4960 KB Output is correct
26 Correct 27 ms 5052 KB Output is correct
27 Correct 22 ms 4856 KB Output is correct
28 Correct 23 ms 4800 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 0 ms 604 KB Output is correct
9 Correct 1 ms 600 KB Output is correct
10 Correct 0 ms 604 KB Output is correct
11 Correct 0 ms 604 KB Output is correct
12 Correct 0 ms 604 KB Output is correct
13 Correct 0 ms 604 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 9 ms 4492 KB Output is correct
17 Correct 16 ms 4696 KB Output is correct
18 Correct 16 ms 4932 KB Output is correct
19 Correct 24 ms 4920 KB Output is correct
20 Correct 18 ms 4344 KB Output is correct
21 Correct 26 ms 5052 KB Output is correct
22 Correct 28 ms 5012 KB Output is correct
23 Correct 26 ms 4956 KB Output is correct
24 Correct 23 ms 4292 KB Output is correct
25 Correct 27 ms 4960 KB Output is correct
26 Correct 27 ms 5052 KB Output is correct
27 Correct 22 ms 4856 KB Output is correct
28 Correct 23 ms 4800 KB Output is correct
29 Correct 1941 ms 85736 KB Output is correct
30 Correct 2418 ms 88608 KB Output is correct
31 Correct 1911 ms 90180 KB Output is correct
32 Correct 2230 ms 90116 KB Output is correct
33 Correct 1586 ms 78928 KB Output is correct
34 Correct 2415 ms 90340 KB Output is correct
35 Correct 3316 ms 105812 KB Output is correct
36 Correct 3077 ms 100452 KB Output is correct
37 Correct 3764 ms 106008 KB Output is correct