This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 >> h >> w;
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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |