Submission #678852

#	Time	Username	Problem	Language	Result	Execution time	Memory
678852		bebra	The Kingdom of JOIOI (JOI17_joioi)	C++17	100 / 100	2465 ms	58796 KiB

joioi

#include <bits/stdc++.h>
using namespace std;

#define dbg(x) cerr << #x << ": " << x << endl;

const int MAX_N = 2000 + 5;
int grid[MAX_N][MAX_N];
bool used[MAX_N][MAX_N];


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> grid[i][j];
        }
    }
    auto check = [&](int x) {
        bool ok = false;
        // // 1)
        // {
        //     int first_min = 1e9;
        //     int first_max = 0;
        //     int last_used = m - 1;
        //     for (int i = 0; i < n; ++i) {
        //         int prev_used = last_used;
        //         for (int j = 0; j <= prev_used; ++j) {
        //             int curr_min = min(first_min, grid[i][j]);
        //             int curr_max = max(first_max, grid[i][j]);
        //             if (curr_max - curr_min > x) {
        //                 last_used = j - 1;
        //                 break;
        //             } else {
        //                 first_min = curr_min;
        //                 first_max = curr_max;
        //                 last_used = j;
        //                 used[i][j] = true;
        //             }
        //         }
        //     }
        //     int second_min = 1e9;
        //     int second_max = 0;
        //     for (int i = 0; i < n; ++i) {
        //         for (int j = 0; j < m; ++j) {
        //             if (!used[i][j]) {
        //                 second_min = min(second_min, grid[i][j]);
        //                 second_max = max(second_max, grid[i][j]);
        //             } else {
        //                 used[i][j] = false;
        //             }
        //         }
        //     }
        //     ok |= second_max - second_min <= x;
        // }
        // 2)
        {
            int first_min = 1e9;
            int first_max = 0;
            int last_used = 0;
            for (int i = 0; i < n; ++i) {
                int prev_used = last_used;
                for (int j = m - 1; j >= prev_used; --j) {
                    int curr_min = min(first_min, grid[i][j]);
                    int curr_max = max(first_max, grid[i][j]);
                    if (curr_max - curr_min > x) {
                        last_used = j + 1;
                        break;
                    } else {
                        first_min = curr_min;
                        first_max = curr_max;
                        last_used = j;
                        used[i][j] = true;
                    }
                }
            }
            int second_min = 1e9;
            int second_max = 0;
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < m; ++j) {
                    if (!used[i][j]) {
                        second_min = min(second_min, grid[i][j]);
                        second_max = max(second_max, grid[i][j]);
                    } else {
                        used[i][j] = false;
                    }
                }
            }
            ok |= second_max - second_min <= x;
        }
        // // 3)
        // {
        //     int first_min = 1e9;
        //     int first_max = 0;
        //     int last_used = m - 1;
        //     for (int i = n - 1; i >= 0; --i) {
        //         int prev_used = last_used;
        //         for (int j = 0; j <= prev_used; ++j) {
        //             int curr_min = min(first_min, grid[i][j]);
        //             int curr_max = max(first_max, grid[i][j]);
        //             if (curr_max - curr_min > x) {
        //                 last_used = j - 1;
        //                 break;
        //             } else {
        //                 first_min = curr_min;
        //                 first_max = curr_max;
        //                 last_used = j;
        //                 used[i][j] = true;
        //             }
        //         }
        //     }
        //     int second_min = 1e9;
        //     int second_max = 0;
        //     for (int i = 0; i < n; ++i) {
        //         for (int j = 0; j < m; ++j) {
        //             if (!used[i][j]) {
        //                 second_min = min(second_min, grid[i][j]);
        //                 second_max = max(second_max, grid[i][j]);
        //             } else {
        //                 used[i][j] = false;
        //             }
        //         }
        //     }
        //     ok |= second_max - second_min <= x;
        // }
        // 4)
        {
            int first_min = 1e9;
            int first_max = 0;
            int last_used = 0;
            for (int i = n - 1; i >= 0; --i) {
                int prev_used = last_used;
                for (int j = m - 1; j >= prev_used; --j) {
                    int curr_min = min(first_min, grid[i][j]);
                    int curr_max = max(first_max, grid[i][j]);
                    if (curr_max - curr_min > x) {
                        last_used = j + 1;
                        break;
                    } else {
                        first_min = curr_min;
                        first_max = curr_max;
                        last_used = j;
                        used[i][j] = true;
                    }
                }
            }
            int second_min = 1e9;
            int second_max = 0;
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < m; ++j) {
                    if (!used[i][j]) {
                        second_min = min(second_min, grid[i][j]);
                        second_max = max(second_max, grid[i][j]);
                    } else {
                        used[i][j] = false;
                    }
                }
            }
            ok |= second_max - second_min <= x;
        }
        // // 5)
        // {
        //     int first_min = 1e9;
        //     int first_max = 0;
        //     int last_used = n - 1;
        //     for (int j = 0; j < m; ++j) {
        //         int prev_used = last_used;
        //         for (int i = 0; i <= prev_used; ++i) {
        //             int curr_min = min(first_min, grid[i][j]);
        //             int curr_max = max(first_max, grid[i][j]);
        //             if (curr_max - curr_min > x) {
        //                 last_used = i - 1;
        //                 break;
        //             } else {
        //                 first_min = curr_min;
        //                 first_max = curr_max;
        //                 last_used = i;
        //                 used[i][j] = true;
        //             }
        //         }
        //     }
        //     int second_min = 1e9;
        //     int second_max = 0;
        //     for (int i = 0; i < n; ++i) {
        //         for (int j = 0; j < m; ++j) {
        //             if (!used[i][j]) {
        //                 second_min = min(second_min, grid[i][j]);
        //                 second_max = max(second_max, grid[i][j]);
        //             } else {
        //                 used[i][j] = false;
        //             }
        //         }
        //     }
        //     ok |= second_max - second_min <= x;
        // }
        // 6)
        {
            int first_min = 1e9;
            int first_max = 0;
            int last_used = n - 1;
            for (int j = m - 1; j >= 0; --j) {
                int prev_used = last_used;
                for (int i = 0; i <= prev_used; ++i) {
                    int curr_min = min(first_min, grid[i][j]);
                    int curr_max = max(first_max, grid[i][j]);
                    if (curr_max - curr_min > x) {
                        last_used = i - 1;
                        break;
                    } else {
                        first_min = curr_min;
                        first_max = curr_max;
                        last_used = i;
                        used[i][j] = true;
                    }
                }
            }
            int second_min = 1e9;
            int second_max = 0;
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < m; ++j) {
                    if (!used[i][j]) {
                        second_min = min(second_min, grid[i][j]);
                        second_max = max(second_max, grid[i][j]);
                    } else {
                        used[i][j] = false;
                    }
                }
            }
            ok |= second_max - second_min <= x;
        }
        // // 7)
        // {
        //     int first_min = 1e9;
        //     int first_max = 0;
        //     int last_used = 0;
        //     for (int j = 0; j < m; ++j) {
        //         int prev_used = last_used;
        //         for (int i = n - 1; i >= prev_used; --i) {
        //             int curr_min = min(first_min, grid[i][j]);
        //             int curr_max = max(first_max, grid[i][j]);
        //             if (curr_max - curr_min > x) {
        //                 last_used = i + 1;
        //                 break;
        //             } else {
        //                 first_min = curr_min;
        //                 first_max = curr_max;
        //                 last_used = i;
        //                 used[i][j] = true;
        //             }
        //         }
        //     }
        //     int second_min = 1e9;
        //     int second_max = 0;
        //     for (int i = 0; i < n; ++i) {
        //         for (int j = 0; j < m; ++j) {
        //             if (!used[i][j]) {
        //                 second_min = min(second_min, grid[i][j]);
        //                 second_max = max(second_max, grid[i][j]);
        //             } else {
        //                 used[i][j] = false;
        //             }
        //         }
        //     }
        //     ok |= second_max - second_min <= x;
        // }
        // 8)
        {
            int first_min = 1e9;
            int first_max = 0;
            int last_used = 0;
            for (int j = m - 1; j >= 0; --j) {
                int prev_used = last_used;
                for (int i = n - 1; i >= prev_used; --i) {
                    int curr_min = min(first_min, grid[i][j]);
                    int curr_max = max(first_max, grid[i][j]);
                    if (curr_max - curr_min > x) {
                        last_used = i + 1;
                        break;
                    } else {
                        first_min = curr_min;
                        first_max = curr_max;
                        last_used = i;
                        used[i][j] = true;
                    }
                }
            }
            int second_min = 1e9;
            int second_max = 0;
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < m; ++j) {
                    if (!used[i][j]) {
                        second_min = min(second_min, grid[i][j]);
                        second_max = max(second_max, grid[i][j]);
                    } else {
                        used[i][j] = false;
                    }
                }
            }
            ok |= second_max - second_min <= x;
        }
        return ok;
    };
    int l = -1;
    int r = 1e9 + 1;
    while (l != r - 1) {
        int mid = (l + r) / 2;
        if (check(mid)) {
            r = mid;
        } else {
            l = mid;
        }
    }
    cout << r << '\n';
    return 0;
}

/*
1 5
1 2 1 2 1
*/

• Subtask 1: 15 / 15
• Subtask 2: 45 / 45
• Subtask 3: 40 / 40