#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector <int>;
using ii = pair <int, int>;
using vii = vector <ii>;
using lii = pair <int, ii>;
const int INF = 1E9+16;
const int MAXN = 2E3+16;
int mat[MAXN][MAXN];
int minX[MAXN][MAXN];
bool vis[MAXN][MAXN];
int main () {
cin.tie(nullptr) -> sync_with_stdio(false);
ll n, m;
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> mat[i][j];
}
}
vector <lii> th, th2;
auto fgetAns = [&]() {
lii maxN = { 0, { -15, -15 } };
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
maxN = max(maxN, { mat[i][j], { i, j } });
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
minX[i][j] = min((i == 0 ? INF : minX[i-1][j]), (j == 0 ? INF : minX[i][j-1]));
minX[i][j] = min(minX[i][j], mat[i][j]);
// cerr << mat[i][j] << ' ';
}
// cerr << '\n';
}
int pans = INF;
th.clear(); th2.clear();
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
vis[i][j] = false;
th.push_back({ minX[i][j], { i, j } });
th2.push_back({ mat[i][j], { i, j } });
}
}
int cl = 0, cr = n*m-1;
int base = minX[maxN.second.first][maxN.second.second];
sort(th.rbegin(), th.rend());
sort(th2.begin(), th2.end());
for (auto [val, ppair] : th) {
auto [i, j] = ppair;
base = min(base, val);
vis[i][j] = true;
while (vis[th2[cr].second.first][th2[cr].second.second]) cr--;
while (vis[th2[cl].second.first][th2[cl].second.second]) cl++;
pans = min(pans, max(maxN.first - base, th2[cr].first - th2[cl].first));
if (cl == cr) break;
}
return pans;
};
int ans = INF;
// cerr << fgetAns() << '\n';
ans = min(ans, fgetAns());
for (int i = 0; i < n; i++) {
for (int j = 0; 2*j < m; j++) {
swap(mat[i][j], mat[i][m-1-j]);
}
}
// cerr << fgetAns() << '\n';
ans = min(ans, fgetAns());
for (int i = 0; 2*i < n; i++) {
for (int j = 0; j < m; j++) {
swap(mat[i][j], mat[n-1-i][j]);
}
}
// cerr << fgetAns() << '\n';
ans = min(ans, fgetAns());
for (int i = 0; i < n; i++) {
for (int j = 0; 2*j < m; j++) {
swap(mat[i][j], mat[i][m-1-j]);
}
}
// cerr << fgetAns() << '\n';
ans = min(ans, fgetAns());
cout << ans << '\n';
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |