Submission #1067154

#TimeUsernameProblemLanguageResultExecution timeMemory
1067154phoenixThe Kingdom of JOIOI (JOI17_joioi)C++17
100 / 100
327 ms54772 KiB
#include <bits/stdc++.h> using namespace std; const int NAX_N = 2020; int n, m; int a[NAX_N][NAX_N]; int mn_r, mn_c; bool check0(int d) { int prev = m; int mn = 1e9, mx = -1e9; for (int r = 0; r < n; r++) { int c = 0; while (c < prev && a[r][c] <= a[mn_r][mn_c] + d) c++; if (r <= mn_r && c <= mn_c) return false; prev = c; while (c < m) { mn = min(mn, a[r][c]); mx = max(mx, a[r][c]); c++; } } return mn + d >= mx; } bool check1(int d) { int prev = -1; int mn = 1e9, mx = -1e9; for (int r = n - 1; r >= 0; r--) { int c = m - 1; while (c > prev && a[r][c] <= a[mn_r][mn_c] + d) c--; if (r >= mn_r && c >= mn_c) return false; prev = c; while (c >= 0) { mn = min(mn, a[r][c]); mx = max(mx, a[r][c]); c--; } } return mn + d >= mx; } bool check2(int d) { int prev = m; int mn = 1e9, mx = -1e9; for (int r = n - 1; r >= 0; r--) { int c = 0; while (c < prev && a[r][c] <= a[mn_r][mn_c] + d) c++; if (r >= mn_r && c <= mn_c) return false; prev = c; while (c < m) { mn = min(mn, a[r][c]); mx = max(mx, a[r][c]); c++; } } return mn + d >= mx; } bool check3(int d) { int prev = -1; int mn = 1e9, mx = -1e9; for (int r = 0; r < n; r++) { int c = m - 1; while (c > prev && a[r][c] <= a[mn_r][mn_c] + d) c--; if (r <= mn_r && c >= mn_c) return false; prev = c; while (c >= 0) { mn = min(mn, a[r][c]); mx = max(mx, a[r][c]); c--; } } return mn + d >= mx; } int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> m; for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) { cin >> a[i][j]; if (a[i][j] < a[mn_r][mn_c]) { mn_r = i; mn_c = j; } } int l = -1, r = 1e9; while (r - l > 1) { int m = (l + r) / 2; if (check0(m) || check1(m) || check2(m) || check3(m)) r = m; else l = m; } cout << r; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...