Submission #140843

#TimeUsernameProblemLanguageResultExecution timeMemory
140843DrumpfTheGodEmperorThe Kingdom of JOIOI (JOI17_joioi)C++14
100 / 100
990 ms39404 KiB
#include <bits/stdc++.h> #define bp __builtin_popcountll #define pb push_back #define in(s) freopen(s, "r", stdin); #define out(s) freopen(s, "w", stdout); #define inout(s, end1, end2) freopen((string(s) + "." + end1).c_str(), "r", stdin),\ freopen((string(s) + "." + end2).c_str(), "w", stdout); #define fi first #define se second #define bw(i, r, l) for (int i = r - 1; i >= l; i--) #define fw(i, l, r) for (int i = l; i < r; i++) #define fa(i, x) for (auto i: x) using namespace std; const int mod = 1e9 + 7, inf = 1061109567; const long long infll = 4557430888798830399; const int N = 2005; int h, w, a[N][N], mn = inf, mni = -1, mnj = -1, mxh[N], mnLand[N], mx = -1; bool testBoard(int direction, int x) { if (direction == 0) { if (mnLand[mnj] < mni) return false; //Below area contains min, upper area contains max. int mnInMaxLand = inf; fw (j, 0, w) { bw (i, h, mnLand[j] + 1) mnInMaxLand = min(mnInMaxLand, a[i][j]); } if (mx - mnInMaxLand <= x) return true; return false; } else { if (mnLand[mnj] > mni) return false; int mnInMaxLand = inf; fw (j, 0, w) { fw (i, 0, mnLand[j]) mnInMaxLand = min(mnInMaxLand, a[i][j]); } if (mx - mnInMaxLand <= x) return true; return false; } } bool check(int x) { if (mx - mn <= x) return true; //Fix below area as land that contains the min element. fw (j, 0, w) { mxh[j] = -1; fw (i, 0, h) { if (a[i][j] > mn + x) break; mxh[j] = i; } } if (mxh[mnj] >= mni) { int curMx = h - 1; fw (j, 0, w) { //Make it decreasing from left to right. mnLand[j] = min(curMx, mxh[j]); curMx = min(curMx, mxh[j]); } if (testBoard(0, x)) return true; curMx = h - 1; bw (j, w, 0) { //Make it decreasing from left to right. mnLand[j] = min(curMx, mxh[j]); curMx = min(curMx, mxh[j]); } if (testBoard(0, x)) return true; } //Fix above area fw (j, 0, w) { mxh[j] = h; bw (i, h, 0) { if (a[i][j] > mn + x) break; mxh[j] = i; } } if (mxh[mnj] <= mni) { int curMx = 0; fw (j, 0, w) { //Make it decreasing from left to right. mnLand[j] = max(curMx, mxh[j]); curMx = max(curMx, mxh[j]); } if (testBoard(1, x)) return true; curMx = 0; bw (j, w, 0) { //Make it decreasing from left to right. mnLand[j] = max(curMx, mxh[j]); curMx = max(curMx, mxh[j]); } if (testBoard(1, x)) return true; } return false; } signed main() { #ifdef BLU in("blu.inp"); #endif ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> h >> w; fw (i, 0, h) fw (j, 0, w) cin >> a[i][j]; fw (i, 0, h) fw (j, 0, w) { if (a[i][j] < mn) { mn = a[i][j]; mni = i, mnj = j; } mx = max(mx, a[i][j]); } int l = 0, r = 1e9; while (l < r) { int m = (l + r) >> 1; if (check(m)) r = m; else l = m + 1; } cout << l; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...