Submission #1066160

#TimeUsernameProblemLanguageResultExecution timeMemory
1066160sammyuriThe Kingdom of JOIOI (JOI17_joioi)C++17
0 / 100
9 ms4540 KiB
#include <bits/stdc++.h> using namespace std; int height[4][2005][2005]; bool taken[2005][2005]; int h, w; bool check(int limit, int index) { memset(taken, false, sizeof(taken)); // first row taken[0][0] = true; for (int j = 1; j < w; j ++) { if (abs(height[index][0][j] - height[index][0][j - 1]) <= limit) taken[0][j] = true; else break; } // subsequent rows for (int i = 1; i < h; i ++) { // ended if (abs(height[index][i][0] - height[index][i - 1][0]) > limit) break; taken[i][0] = true; for (int j = 1; j < w; j ++) { if (taken[i - 1][j] && abs(height[index][0][j] - height[index][0][j - 1]) <= limit) taken[0][j] = true; else break; } } // check the rest is ok for (int i = 0; i < h; i ++) for (int j = 0; j < w - 1; j ++) if (!taken[i][j] && !taken[i][j + 1]) if (abs(height[index][i][j] - height[index][i][j + 1]) > limit) return false; for (int j = 0; j < w; j ++) for (int i = 0; i < h - 1; i ++) if (!taken[i][j] && !taken[i + 1][j]) if (abs(height[index][i][j] - height[index][i + 1][j]) > limit) return false; return true; } bool possible(int limit) { if (check(limit, 0)) return true; if (check(limit, 1)) return true; if (check(limit, 2)) return true; if (check(limit, 3)) return true; return false; } int main() { cin >> w >> h; for (int i = 0; i < h; i ++) { for (int j = 0; j < w; j ++) cin >> height[0][i][j]; } for (int i = 0; i < h; i ++) for (int j = 0; j < w; j ++) height[1][i][j] = height[0][h - i - 1][j], height[2][i][j] = height[0][i][w - j - 1], height[3][i][j] = height[0][h - i - 1][w - j - 1]; int L = 0, R = 1e9 + 5; while (L != R) { int mid = (L + R) / 2; if (possible(mid)) R = mid; else L = mid + 1; } cout << L << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...