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>
#define int long long
using namespace std;
const int INF = 2e18;
const int MAXN = 2e3 + 5;
int n, m, mx, mn;
int a[MAXN][MAXN];
int g[MAXN][MAXN];
void rotate() {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
g[j][n - i + 1] = a[i][j];
}
}
swap(n, m);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
a[i][j] = g[i][j];
}
}
}
bool check(int x) {
int lim = m + 1;
for (int i = 1; i <= n; i++) {
int r = 0;
for (int j = 1; j <= min(lim, m); j++) {
if (mx - x <= a[i][j]) {
r = max(r, j);
} else {
break;
}
}
lim = r;
for (int j = r + 1; j <= m; j++) {
if (a[i][j] - x > mn) {
return false;
}
}
}
return true;
}
int search() {
int l = 0, r = 2e9 + 5;
while (l < r) {
int mid = (l + r) >> 1;
if (check(mid)) {
r = mid;
} else {
l = mid + 1;
}
}
return r;
}
signed main() {
cin >> n >> m;
mx = -INF, mn = INF;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> a[i][j];
mx = max(mx, a[i][j]);
mn = min(mn, a[i][j]);
}
}
int ans = INF;
ans = min(ans, search());
rotate();
ans = min(ans, search());
rotate();
ans = min(ans, search());
rotate();
ans = min(ans, search());
ans = min(mx - mn, ans);
cout << ans << "\n";
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |