#include <bits/stdc++.h>
using namespace std;
#define int long long
bool good(int n, int m, vector<vector<int>> &a, int x) {
int mn = 1e11, mx = -1e11;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
mn = min(mn, a[i][j]);
mx = max(mx, a[i][j]);
}
}
vector<vector<int>> need(n, vector<int>(m));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (a[i][j] <= mx - x) need[i][j] += 1;
if (a[i][j] >= mn + x) need[i][j] += 2;
if (need[i][j] == 3) return 0;
}
}
/*for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
switch (need[i][j]) {
case 0: cout << " "; break;
case 1: cout << "- "; break;
case 2: cout << "+ "; break;
case 3: cout << "± ";
}
}
cout << "\n";
}*/
for (int i = 0; i < n; i++) {
bool ones = 1;
for (int j = 0; j < m; j++) {
if (need[i][j] == 1) {
if (!ones) return 0;
}
if (need[i][j] == 2) {
if (ones) ones = 0;
}
}
}
vector<int> depth(n, -1);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (need[i][j] == 2) break;
if (need[i][j] == 1) depth[i] = j;
if (need[i][j] == 0) depth[i] = min((i > 0 ? depth[i - 1] : (int)(1e9)), j);
}
//cout << depth[i] << " ";
}
//cout << "\n";
for (int i = 0; i < n - 1; i++) {
if (depth[i] < depth[i + 1]) return 0;
}
return 1;
}
int solve(int n, int m, vector<vector<int>> &a) {
/*for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cout << a[i][j] << " ";
}
cout << "\n";
}*/
int l = -1, r = 1e11;
while (r - l > 1) {
int md = (l + r) / 2;
if (good(n, m, a, md)) {
//cout << "Good " << md << "\n";
r = md;
} else {
//cout << "Bad " << md << "\n";
l = md;
}
}
//cout << l << "\n\n";
return l;
}
vector<vector<int>> fliph(int n, int m, vector<vector<int>> &a) {
vector<vector<int>> ans(n, vector<int>(m));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
ans[i][j] = a[i][m - j - 1];
}
}
return ans;
}
vector<vector<int>> flipv(int n, int m, vector<vector<int>> &a) {
vector<vector<int>> ans(n, vector<int>(m));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
ans[i][j] = a[n - 1 - i][j];
}
}
return ans;
}
vector<vector<int>> flips(int n, int m, vector<vector<int>> &a) {
vector<vector<int>> ans(n, vector<int>(m));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
ans[i][j] = -a[i][j];
}
}
return ans;
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<vector<int>> a(n, vector<int>(m));
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
cin >> a[i][j];
int ans = solve(n, m, a);
a = fliph(n, m, a);
ans = min(ans, solve(n, m, a));
a = flipv(n, m, a);
ans = min(ans, solve(n, m, a));
a = fliph(n, m, a);
ans = min(ans, solve(n, m, a));
a = flips(n, m, a);
ans = min(ans, solve(n, m, a));
a = fliph(n, m, a);
ans = min(ans, solve(n, m, a));
a = flipv(n, m, a);
ans = min(ans, solve(n, m, a));
a = fliph(n, m, a);
ans = min(ans, solve(n, m, a));
cout << ans << "\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
