제출 #837276

#제출 시각아이디문제언어결과실행 시간메모리
837276KoyoteThe Kingdom of JOIOI (JOI17_joioi)C++11
100 / 100
1342 ms19988 KiB
#include <bits/stdc++.h> using namespace std; const int maxN = 2e3 + 2; int h, w, a[maxN][maxN], mxA_i; bool b[maxN][maxN]; int main() { cin.tie(nullptr)->sync_with_stdio(false); cin >> h >> w; for (int i = 0; i < h; i++) for (int j = 0; j < w; j++) cin >> a[i][j], mxA_i = max(mxA_i, a[i][j]); auto small_check = [&](int k) { int max_right = w; int mn = int(1e9), mx = 0; for (int i = 0; i < h; i++) { for (int j = 0; j < max_right; j++) if (b[i][j]) max_right = j; for (int j = max_right; j < w; j++) mn = min(mn, a[i][j]), mx = max(mx, a[i][j]); } return mx - mn <= k; }; auto 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]), swap(b[i][j], b[i][w - j - 1]); }; auto 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]), swap(b[i][j], b[h - i - 1][j]); }; auto bin_func = [&](int k) { for (int i = 0; i < h; i++) for (int j = 0; j < w; j++) b[i][j] = (mxA_i - a[i][j] > k); bool res = false; reverse_rows(); res |= small_check(k); reverse_cols(); res |= small_check(k); reverse_rows(); res |= small_check(k); reverse_cols(); res |= small_check(k); return res; }; int lo = 1, hi = int(1e9), ans = hi; while (lo <= hi) { int mid = (lo + hi) >> 1; if (bin_func(mid)) ans = mid, hi = mid - 1; else lo = mid + 1; } cout << ans << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...