#include <bits/stdc++.h>
#define pb push_back
#define all(v) v.begin(), v.end()
#define sz(v) int(v.size())
#define pii pair<int, int>
#define mp make_pair
#define f first
#define ll long long
#define ld long double
#define s second
#define vec vector<int>
using namespace std;
const int N = (int) 2e3 + 10;
const int M = (int) 2018 * 2018;
const int K = (int) 15;
const int INF = (int) 1e9 + 7;
const int mod = (int) 998244353;
const ld EPS = (ld) 1e-9;
const ll LINF = (ll) 1e18;
int n, m;
int a[N][N], ptr[N];
bool boo[N][N];
bool solve(int diff) {
int mx_i = 1, mx_j = 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (a[mx_i][mx_j] < a[i][j]) {
mx_i = i;
mx_j = j;
}
}
}
// a[mx_i][mx_j] <= a[i][j] + diff
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (a[mx_i][mx_j] <= diff + a[i][j]) {
boo[i][j] = 1;
} else {
boo[i][j] = 0;
}
}
}
ptr[0] = m;
for (int i = 1; i <= n; i++) {
ptr[i] = ptr[i - 1];
for (int j = 1; j <= ptr[i - 1]; j++) {
if (!boo[i][j]) {
ptr[i] = j - 1;
break;
}
}
}
int mx = 0, mn = INF;
for (int i = 1; i <= n; i++) {
for (int j = ptr[i] + 1; j <= m; j++) {
mx = max(mx, a[i][j]);
mn = min(mn, a[i][j]);
}
}
if (mx_j > ptr[mx_i])
return false;
return mx - mn <= diff;
}
void mirror() {
for (int i = 1; i <= n / 2; i++) {
for (int j = 1; j <= m; j++) {
swap(a[i][j], a[n - i + 1][j]);
}
}
}
void rotate() {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
a[j][n - i + 1] = a[i][j];
}
}
swap(n, m);
}
bool ok(int diff) {
bool ok = false;
for (int i = 0; i < 4; i++) {
ok |= solve(diff);
mirror();
ok |= solve(diff);
mirror();
rotate();
}
return ok;
}
int main() {
#ifdef sony
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
srand(time(0));
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
scanf("%d", &a[i][j]);
}
}
int l = 1, r = INF;
int ans;
while (l <= r) {
int mid = (l + r) / 2;
if (ok(mid)) {
r = mid - 1;
ans = mid;
} else {
l = mid + 1;
}
}
cout << ans;
return 0;
}
Compilation message
joioi.cpp: In function 'int main()':
joioi.cpp:108:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &a[i][j]);
~~~~~^~~~~~~~~~~~~~~~
joioi.cpp:122:7: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
cout << ans;
~~~~~^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 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 |
376 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 |
376 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
