#include<bits/stdc++.h>
#define pb emplace_back
#define mp make_pair
#define fi first
#define se second
#define ll long long
using namespace std;
const int N = int(2e3) + 7;
const int inf = int(1e9) + 7;
int n, m, a[N][N], mn, mx, res;
int lefMin[N], lefMax[N], rigMax[N], rigMin[N];
bool Check(int dif) {
int lim = mn + dif;
int Mx = 0, Mn = inf;
for(int j = 0; j < m; ++j) {
if(a[0][j] > lim) {
Mx = max(Mx, rigMax[j]);
Mn = min(Mn, rigMin[j]);
if(Mx - Mn <= dif) return 1;
Mx = lefMax[j], Mn = lefMin[j]; continue;
}
bool divided = 0;
for(int i = 0; i < n; ++i) {
if(a[i][j] <= lim && !divided) continue;
Mx = max(Mx, a[i][j]), Mn = min(Mn, a[i][j]);
divided = 1;
}
}
return Mx - Mn <= dif;
}
void Solve() {
fill_n(rigMax, m + 1, 0);
fill_n(rigMin, m + 1, inf);
fill_n(lefMax, m + 1, 0);
fill_n(lefMin, m + 1, inf);
for(int i = n - 1; i >= 0; --i) {
for(int j = 0; j < m; ++j) {
if(j) {
lefMax[j] = max({lefMax[j], lefMax[j - 1], a[i][j]});
lefMin[j] = min({lefMax[j], lefMin[j - 1], a[i][j]});
} else {
lefMax[j] = max(lefMax[j], a[i][j]);
lefMin[j] = min(lefMin[j], a[i][j]);
}
}
for(int j = m - 1; j >= 0; --j) {
if(j + 1 < m) {
rigMax[j] = max({rigMax[j], rigMax[j + 1], a[i][j]});
rigMin[j] = min({rigMin[j], rigMin[j + 1], a[i][j]});
} else {
rigMax[j] = max(rigMax[j], a[i][j]);
rigMin[j] = min(rigMin[j], a[i][j]);
}
}
}
int low, high, mid;
low = 0, high = mx - mn;
while(low <= high) {
mid = (low + high) >> 1;
if(Check(mid)) high = mid - 1;
else low = mid + 1;
}
res = min(res, low);
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
if(fopen("test.inp", "r")) {
freopen("test.inp", "r", stdin);
freopen("test.out", "w", stdout);
}
cin >> n >> m; mn = inf, mx = 0;
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]);
}
}
res = mx - mn;
Solve();
for(int j = 0; j < m; ++j) {
for(int i = 0; n - 1 - i > i; ++i) {
swap(a[i][j], a[n - 1 - i][j]);
}
}
Solve();
cout << res;
}
Compilation message
joioi.cpp: In function 'int main()':
joioi.cpp:75:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen("test.inp", "r", stdin);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
joioi.cpp:76:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen("test.out", "w", stdout);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
504 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
504 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
504 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
