제출 #1032916

#제출 시각아이디문제언어결과실행 시간메모리
1032916juicyThe Kingdom of JOIOI (JOI17_joioi)C++17
100 / 100
718 ms55020 KiB
#include <bits/stdc++.h> using namespace std; #ifdef LOCAL #include "debug.h" #else #define debug(...) 42 #endif const int N = 2e3 + 5, inf = 1e9; int n, m, mn = inf, mx; int a[N][N]; bool check(int k) { int cut = 0; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { if (a[i][j] < mx - k) { cut = max(cut, j); } } for (int j = 1; j <= m; ++j) { if (a[i][j] > mn + k && cut >= j) { return 0; } } } return 1; } int solve() { int L = 0, R = mx - mn, res = mx - mn; while (L <= R) { int md = (L + R) / 2; if (check(md)) { res = md; R = md - 1; } else { L = md + 1; } } return res; } void flip_row() { for (int j = 1; j <= m; ++j) { for (int i = 1; i <= n / 2; ++i) { swap(a[i][j], a[n - i + 1][j]); } } } void flip_col() { for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m / 2; ++j) { swap(a[i][j], a[i][m - j + 1]); } } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> m; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { cin >> a[i][j]; mn = min(mn, a[i][j]); mx = max(mx, a[i][j]); } } int res = solve(); flip_row(); res = min(res, solve()); flip_col(); res = min(res, solve()); flip_row(); res = min(res, solve()); cout << res; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...