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 <iostream>
#include <vector>
using namespace std;
const int INF = 1e9 + 1;
int n, m, mn = INF, mx = -INF;
vector<vector<pair<int, int>>> dp;
vector<vector<int>> a, mxr, mnc;
void rotate() {
vector<vector<int>> b(m, vector<int>(n));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
b[j][n - 1 - i] = a[i][j];
}
}
a = b;
swap(n, m);
}
void preprocess() {
mxr.clear();
mxr.resize(n, vector<int>(m));
for (int i = 0; i < n; i++) {
mxr[i][0] = a[i][0];
for (int j = 1; j < m; j++) {
mxr[i][j] = max(mxr[i][j - 1], a[i][j]);
}
}
mnc.clear();
mnc.resize(n, vector<int>(m));
for (int j = 0; j < m; j++) {
mnc[n - 1][j] = a[n - 1][j];
for (int i = n - 2; i >= 0; i--) {
mnc[i][j] = min(mnc[i + 1][j], a[i][j]);
}
}
}
// int minInCol(int i, int j) {
// int ret = INF;
// for (int k = n - 1; k >= i; k--) {
// ret = min(ret, a[k][j]);
// }
// return ret;
// }
// int maxInRow(int i, int j) {
// int ret = 0;
// for (int k = 0; k <= j; k++) {
// ret = max(ret, a[i][k]);
// }
// return ret;
// }
pair<int, int> solve(int i, int j) {
if (i == n) return {-INF, INF};
if (j == -1) return {-INF, INF};
if (dp[i][j].first != INF) return dp[i][j];
pair<int, int> p1 = solve(i + 1, j);
p1.first = max(p1.first, mxr[i][j]);
pair<int, int> p2 = solve(i, j - 1);
p2.second = min(p2.second, mnc[i][j]);
dp[i][j] = max(p1.first - mn, mx - p1.second) < max(p2.first - mn, mx - p2.second) ? p1 : p2;
return dp[i][j];
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
a.resize(n, vector<int>(m));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> a[i][j];
mn = min(mn, a[i][j]);
mx = max(mx, a[i][j]);
}
}
int ans = mx - mn;
for (int _ = 0; _ < 4; _++) {
dp.clear();
dp.resize(n, vector<pair<int, int>>(m, {INF, -INF}));
preprocess();
pair<int, int> res = solve(0, m - 1);
ans = min(ans, max(res.first - mn, mx - res.second));
rotate();
}
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... |