#include<bits/stdc++.h>
using namespace std;
#define i64 long long
#define int long long
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(), (x).end()
void Solve(void) {
int H, W; cin >> H >> W;
vector<vector<int>> a(H + 2, vector<int> (W + 2));
vector<vector<int>> prefmxR(H + 2, vector<int> (W + 2, 0));
vector<vector<int>> suffmxR(H + 2, vector<int> (W + 2, 0));
vector<vector<int>> prefmxC(H + 2, vector<int> (W + 2, 0));
vector<vector<int>> suffmxC(H + 2, vector<int> (W + 2, 0));
vector<vector<int>> prefmnR(H + 2, vector<int> (W + 2, INT_MAX));
vector<vector<int>> suffmnR(H + 2, vector<int> (W + 2, INT_MAX));
vector<vector<int>> prefmnC(H + 2, vector<int> (W + 2, INT_MAX));
vector<vector<int>> suffmnC(H + 2, vector<int> (W + 2, INT_MAX));
for (int i = 1; i <= H; i ++) {
for (int j = 1; j <= W; j ++) {
cin >> a[i][j];
prefmxR[i][j] = max(a[i][j], prefmxR[i][j - 1]);
prefmnR[i][j] = min(a[i][j], prefmnR[i][j - 1]);
}
for (int j = W; j >= 1; j --) {
suffmxR[i][j] = max(a[i][j], suffmxR[i][j + 1]);
suffmnR[i][j] = min(a[i][j], suffmnR[i][j + 1]);
}
}
for (int j = 1; j <= W; j ++) {
for (int i = 1; i <= H; i ++) {
prefmxC[i][j] = max(a[i][j], prefmxC[i - 1][j]);
prefmnC[i][j] = min(a[i][j], prefmnC[i - 1][j]);
}
for (int i = H; i >= 1; i --) {
suffmxC[i][j] = max(a[i][j], suffmxC[i + 1][j]);
suffmnC[i][j] = min(a[i][j], suffmnC[i + 1][j]);
}
}
auto check = [&](int gap) {
for (int i = 1; i <= H; i ++) {
for (int j = 1; j <= W; j ++) {
bool workslf = true, worksrg = true;
if (abs(a[i][j] - prefmnR[i][j]) > gap) workslf = false;
if (abs(a[i][j] - prefmxR[i][j]) > gap) workslf = false;
if (abs(a[i][j] - suffmnR[i][j]) > gap) worksrg = false;
if (abs(a[i][j] - suffmxR[i][j]) > gap) worksrg = false;
if (!(workslf | worksrg)) return false;
}
}
for (int j = 1; j <= W; j ++) {
for (int i = 1; i <= H; i ++) {
bool workslf = true, worksrg = true;
if (abs(a[i][j] - prefmnC[i][j]) > gap) workslf = false;
if (abs(a[i][j] - prefmxC[i][j]) > gap) workslf = false;
if (abs(a[i][j] - suffmnC[i][j]) > gap) worksrg = false;
if (abs(a[i][j] - suffmxC[i][j]) > gap) worksrg = false;
if (!(workslf | worksrg)) return false;
}
}
return true;
};
int l = 0, h = 1000000000;
while (l <= h) {
int mid = (l + h)/2;
if (check(mid)) h = mid - 1;
else l = mid + 1;
}
cout << l << "\n";
}
signed main() {
ios_base::sync_with_stdio(false); cin.tie(0);
int Tests = 1; // cin >> Tests;
while (Tests --) {
Solve();
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
352 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
352 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
352 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
