#include <stdio.h>
#define N 2000
#define M 2000
#define INF 0x3f3f3f3f
int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }
int aa[N][M], aa_[N][M], n, m, d;
int solve_(int d) {
static char good[N][M * 2];
int i, j, k, s, t, mn, mx;
mn = INF, mx = -1;
for (i = 0; i < n; i++)
for (j = 0; j < m; j++)
mn = min(mn, aa_[i][j]), mx = max(mx, aa_[i][j]);
for (i = 0; i < n; i++) {
k = 0;
for (j = 0; j < m; j++)
if (mx - aa_[i][j] > d)
k++;
for (j = 0; j < m; j++) {
good[i][j] = k == 0;
if (mx - aa_[i][j] > d)
k--;
if (aa_[i][j] - mn > d)
k++;
}
for (j = 0; j < m; j++) {
good[i][m + j] = k == 0;
if (aa_[i][j] - mn > d)
k--;
if (mx - aa_[i][j] > d)
k++;
}
}
for (s = 0; s < m * 2; s++) {
t = s + m;
for (i = 0, j = s; i < n && j < t; i++)
while (j < t && !good[i][j % (m * 2)])
j++;
if (j < t)
return 1;
}
return 0;
}
int solve(int d) {
int h, i, j, jl, jr, tmp;
for (i = 0; i < n; i++)
for (j = 0; j < m; j++)
aa_[i][j] = aa[i][j];
for (h = 0; h < 2; h++) {
if (solve_(d))
return 1;
for (i = 0; i < n; i++)
for (jl = 0, jr = m - 1; jl < jr; jl++, jr--)
tmp = aa_[i][jl], aa_[i][jl] = aa_[i][jr], aa_[i][jr] = tmp;
}
return 0;
}
int main() {
int i, j, lower, upper;
scanf("%d%d", &n, &m);
for (i = 0; i < n; i++)
for (j = 0; j < m; j++)
scanf("%d", &aa[i][j]);
lower = -1, upper = INF;
while (upper - lower > 1) {
int d = (lower + upper) / 2;
if (solve(d))
upper = d;
else
lower = d;
}
printf("%d\n", upper);
return 0;
}
Compilation message
joioi.c: In function 'main':
joioi.c:70:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
70 | scanf("%d%d", &n, &m);
| ^~~~~~~~~~~~~~~~~~~~~
joioi.c:73:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
73 | scanf("%d", &aa[i][j]);
| ^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
