#include <bits/stdc++.h>
using namespace std;
#define dbg(x) cerr << #x << ": " << x << endl;
const int MAX_N = 2000 + 5;
int grid[MAX_N][MAX_N];
bool used[MAX_N][MAX_N];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cin >> grid[i][j];
}
}
auto check = [&](int x) {
bool ok = false;
// 1)
{
int first_min = 1e9;
int first_max = 0;
int last_used = m - 1;
for (int i = 0; i < n; ++i) {
int prev_used = last_used;
for (int j = 0; j <= prev_used; ++j) {
int curr_min = min(first_min, grid[i][j]);
int curr_max = max(first_max, grid[i][j]);
if (curr_max - curr_min > x) {
break;
} else {
first_min = curr_min;
first_max = curr_max;
last_used = j;
used[i][j] = true;
}
}
}
int second_min = 1e9;
int second_max = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (!used[i][j]) {
second_min = min(second_min, grid[i][j]);
second_max = max(second_max, grid[i][j]);
}
}
}
memset(used, 0, sizeof(used));
ok |= second_max - second_min <= x;
}
// 2)
{
int first_min = 1e9;
int first_max = 0;
int last_used = 0;
for (int i = 0; i < n; ++i) {
int prev_used = last_used;
for (int j = m - 1; j >= prev_used; --j) {
int curr_min = min(first_min, grid[i][j]);
int curr_max = max(first_max, grid[i][j]);
if (curr_max - curr_min > x) {
break;
} else {
first_min = curr_min;
first_max = curr_max;
last_used = j;
used[i][j] = true;
}
}
}
int second_min = 1e9;
int second_max = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (!used[i][j]) {
second_min = min(second_min, grid[i][j]);
second_max = max(second_max, grid[i][j]);
}
}
}
memset(used, 0, sizeof(used));
ok |= second_max - second_min <= x;
}
// 3)
{
int first_min = 1e9;
int first_max = 0;
int last_used = m - 1;
for (int i = n - 1; i >= 0; --i) {
int prev_used = last_used;
for (int j = 0; j <= prev_used; ++j) {
int curr_min = min(first_min, grid[i][j]);
int curr_max = max(first_max, grid[i][j]);
if (curr_max - curr_min > x) {
break;
} else {
first_min = curr_min;
first_max = curr_max;
last_used = j;
used[i][j] = true;
}
}
}
int second_min = 1e9;
int second_max = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (!used[i][j]) {
second_min = min(second_min, grid[i][j]);
second_max = max(second_max, grid[i][j]);
}
}
}
memset(used, 0, sizeof(used));
ok |= second_max - second_min <= x;
}
// 4)
{
int first_min = 1e9;
int first_max = 0;
int last_used = 0;
for (int i = n - 1; i >= 0; --i) {
int prev_used = last_used;
for (int j = m - 1; j >= prev_used; --j) {
int curr_min = min(first_min, grid[i][j]);
int curr_max = max(first_max, grid[i][j]);
if (curr_max - curr_min > x) {
break;
} else {
first_min = curr_min;
first_max = curr_max;
last_used = j;
used[i][j] = true;
}
}
}
int second_min = 1e9;
int second_max = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (!used[i][j]) {
second_min = min(second_min, grid[i][j]);
second_max = max(second_max, grid[i][j]);
}
}
}
memset(used, 0, sizeof(used));
ok |= second_max - second_min <= x;
}
// 5)
{
int first_min = 1e9;
int first_max = 0;
int last_used = n - 1;
for (int j = 0; j < m; ++j) {
int prev_used = last_used;
for (int i = 0; i <= prev_used; ++i) {
int curr_min = min(first_min, grid[i][j]);
int curr_max = max(first_max, grid[i][j]);
if (curr_max - curr_min > x) {
break;
} else {
first_min = curr_min;
first_max = curr_max;
last_used = i;
used[i][j] = true;
}
}
}
int second_min = 1e9;
int second_max = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (!used[i][j]) {
second_min = min(second_min, grid[i][j]);
second_max = max(second_max, grid[i][j]);
}
}
}
memset(used, 0, sizeof(used));
ok |= second_max - second_min <= x;
}
// 6)
{
int first_min = 1e9;
int first_max = 0;
int last_used = n - 1;
for (int j = m - 1; j >= 0; --j) {
int prev_used = last_used;
for (int i = 0; i <= prev_used; ++i) {
int curr_min = min(first_min, grid[i][j]);
int curr_max = max(first_max, grid[i][j]);
if (curr_max - curr_min > x) {
break;
} else {
first_min = curr_min;
first_max = curr_max;
last_used = i;
used[i][j] = true;
}
}
}
int second_min = 1e9;
int second_max = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (!used[i][j]) {
second_min = min(second_min, grid[i][j]);
second_max = max(second_max, grid[i][j]);
}
}
}
memset(used, 0, sizeof(used));
ok |= second_max - second_min <= x;
}
// 7)
{
int first_min = 1e9;
int first_max = 0;
int last_used = 0;
for (int j = 0; j < m; ++j) {
int prev_used = last_used;
for (int i = n - 1; i >= prev_used; --i) {
int curr_min = min(first_min, grid[i][j]);
int curr_max = max(first_max, grid[i][j]);
if (curr_max - curr_min > x) {
break;
} else {
first_min = curr_min;
first_max = curr_max;
last_used = i;
used[i][j] = true;
}
}
}
int second_min = 1e9;
int second_max = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (!used[i][j]) {
second_min = min(second_min, grid[i][j]);
second_max = max(second_max, grid[i][j]);
}
}
}
memset(used, 0, sizeof(used));
ok |= second_max - second_min <= x;
}
// 8)
{
int first_min = 1e9;
int first_max = 0;
int last_used = 0;
for (int j = m - 1; j >= 0; --j) {
int prev_used = last_used;
for (int i = n - 1; i >= prev_used; --i) {
int curr_min = min(first_min, grid[i][j]);
int curr_max = max(first_max, grid[i][j]);
if (curr_max - curr_min > x) {
break;
} else {
first_min = curr_min;
first_max = curr_max;
last_used = i;
used[i][j] = true;
}
}
}
int second_min = 1e9;
int second_max = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (!used[i][j]) {
second_min = min(second_min, grid[i][j]);
second_max = max(second_max, grid[i][j]);
}
}
}
memset(used, 0, sizeof(used));
ok |= second_max - second_min <= x;
}
return ok;
};
int l = -1;
int r = 1e9 + 1;
while (l != r - 1) {
int mid = (l + r) / 2;
if (check(mid)) {
r = mid;
} else {
l = mid;
}
}
cout << r << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
27 ms |
4180 KB |
Output is correct |
| 2 |
Correct |
25 ms |
4292 KB |
Output is correct |
| 3 |
Incorrect |
28 ms |
4180 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
27 ms |
4180 KB |
Output is correct |
| 2 |
Correct |
25 ms |
4292 KB |
Output is correct |
| 3 |
Incorrect |
28 ms |
4180 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
27 ms |
4180 KB |
Output is correct |
| 2 |
Correct |
25 ms |
4292 KB |
Output is correct |
| 3 |
Incorrect |
28 ms |
4180 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
