Submission #678847

#TimeUsernameProblemLanguageResultExecution timeMemory
678847bebraThe Kingdom of JOIOI (JOI17_joioi)C++17
0 / 100
28 ms4292 KiB
#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) { 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]); } } } memset(used, 0, sizeof(used)); 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) { 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]); } } } memset(used, 0, sizeof(used)); 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) { 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]); } } } memset(used, 0, sizeof(used)); 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) { 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]); } } } memset(used, 0, sizeof(used)); 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) { 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]); } } } memset(used, 0, sizeof(used)); 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) { 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]); } } } memset(used, 0, sizeof(used)); 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) { 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]); } } } memset(used, 0, sizeof(used)); 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) { 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]); } } } memset(used, 0, sizeof(used)); 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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...