Submission #685110

#TimeUsernameProblemLanguageResultExecution timeMemory
685110coffee5427The Kingdom of JOIOI (JOI17_joioi)C++17
100 / 100
1654 ms65908 KiB
#include <bits/stdc++.h> #define int long long #define pii pair<int, int> #define pb push_back #define mk make_pair #define F first #define S second #define ALL(x) x.begin(), x.end() using namespace std; using PQ = priority_queue<int, vector<int>, greater<int>>; const int INF = 2e18; const int maxn = 2e3 + 5; const int M = 1e9 + 7; int n, m, mx, mn; int a[maxn][maxn]; int g[maxn][maxn]; void rotate () { // (3, 2) -> (2, 3) // (X, Y) -> (n - Y + 1, X) // (Y, X) -> (X, n - Y + 1) // (1, 4) -> (2, 3) for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { g[j][n - i + 1] = a[i][j]; } } swap (n, m); for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { a[i][j] = g[i][j]; } } } int check (int x) { int lim = m + 1; for (int i = 1; i <= n; i++) { int r = 0; for (int j = 1; j <= min (lim, m); j++) { if (mx - x <= a[i][j]) r = max (r, j); else break; } lim = r; for (int j = r + 1; j <= m; j++) { if (a[i][j] - x > mn) return 0; } } return 1; } int search () { int l = 0, r = 2e9 + 5; while (l < r) { int mid = (l + r) >> 1; if (check (mid)) r = mid; else l = mid + 1; } return r; } void init () { cin >> n >> m; mx = -INF, mn = INF; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { cin >> a[i][j]; mx = max (mx, a[i][j]); mn = min (mn, a[i][j]); } } } void solve () { int ans = INF; ans = min (ans, search ()); rotate (); ans = min (ans, search ()); rotate (); ans = min (ans, search ()); rotate (); ans = min (ans, search ()); cout << ans << "\n"; } signed main() { // ios::sync_with_stdio(0); // cin.tie(0); int t = 1; //cin >> t; while (t--) { init(); solve(); } } /* 4 4 1 12 6 11 11 10 2 14 10 1 9 20 4 17 19 10 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...