#include <bits/stdc++.h>
using namespace std;
int n, m;
const int MXN = 2005;
int arr[MXN][MXN];
int mn = INT_MAX, mx = INT_MIN, ans;
int pfmax[MXN][MXN];
int sfmin[MXN][MXN];
bool works(int k) {
int last_used = INT_MAX;
for (int i=1; i<=n; i++) {
int pos = 0;
while (pos + 1 <= m && pfmax[i][pos] <= mn + k) {
pos++;
}
pos = min(pos, last_used);
if (sfmin[i][pos+1] < mx - k) {
return false;
}
}
return true;
}
void prep() {
for (int i=1; i<=n; i++) {
pfmax[i][0] = INT_MIN;
pfmax[i][1] = arr[i][1];
for (int j=2; j<=m; j++) {
pfmax[i][j] = max(pfmax[i][j-1], arr[i][j]);
}
sfmin[i][m+1] = INT_MAX;
sfmin[i][m] = arr[i][m];
for (int j=m-1; j>=1; j--) {
sfmin[i][j] = min(sfmin[i][j+1], arr[i][j]);
}
}
}
int copytemp[MXN][MXN];
void rot() {
for (int i=1; i<=n; i++) {
for (int j=1; j<=m; j++) {
copytemp[j][n-i+1] = arr[i][j];
}
}
swap(n, m);
for (int i=1; i<=n; i++) {
for (int j=1; j<=m; j++) {
arr[i][j] = copytemp[i][j];
}
}
}
signed main() {
cin >> n >> m;
for (int i=1; i<=n; i++) {
for (int j=1; j<=m; j++) {
cin >> arr[i][j];
mn = min(mn, arr[i][j]);
mx = max(mx, arr[i][j]);
}
}
ans = mx - mn;
for (int X=0; X<4; X++) {
prep();
int low = 0;
int high = INT_MAX / 2;
while (low + 1 < high) {
int mid = (low + high) / 2;
if (works(mid)) {
high = mid;
}
else {
low = mid;
}
}
if (works(low)) ans = min(ans, low);
else ans = min(ans, high);
rot();
}
cout << ans << endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
