#include <iostream>
#include <iomanip>
using namespace std;
#define INF 1000000001
int n, m, i, j, a[2010][2010], ao[2010][2010], av[2010][2010], ac[2010][2010];
int mini = INF, maxi = 0, st, dr, mij, sol;
bool testDiff (int x, int (&a)[2010][2010])
{
int prevh = n;
for (j = 1; j <= m; j++) {
for (i = 1; i <= prevh; i++) {
if (a[i][j] > mini+x)
break;
}
prevh = i-1;
for (; i <= n; i++) {
if (a[i][j] < maxi-x)
return false;
}
}
return true;
}
bool testAllDiff (int x)
{
return (testDiff(x, a) || testDiff(x, ao) || testDiff(x, av) || testDiff(x, ac));
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
for (i = 1; i <= n; i++) {
for (j = 1; j <= m; j++) {
cin >> a[i][j];
mini = min(mini, a[i][j]);
maxi = max(maxi, a[i][j]);
ao[n-i+1][j] = a[i][j];
av[i][m-j+1] = a[i][j];
ac[n-i+1][m-j+1] = a[i][j];
}
}
st = 0;
dr = maxi-mini;
sol = -1;
while (st <= dr) {
mij = (st+dr) / 2;
bool ok = testAllDiff(mij);
if (ok) {
sol = mij;
dr = mij-1;
}
else {
st = mij+1;
}
}
cout << sol;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
468 KB |
Output is correct |
3 |
Correct |
1 ms |
468 KB |
Output is correct |
4 |
Correct |
1 ms |
468 KB |
Output is correct |
5 |
Correct |
1 ms |
468 KB |
Output is correct |
6 |
Correct |
1 ms |
468 KB |
Output is correct |
7 |
Correct |
1 ms |
468 KB |
Output is correct |
8 |
Correct |
1 ms |
468 KB |
Output is correct |
9 |
Correct |
1 ms |
468 KB |
Output is correct |
10 |
Correct |
1 ms |
468 KB |
Output is correct |
11 |
Correct |
1 ms |
468 KB |
Output is correct |
12 |
Correct |
1 ms |
456 KB |
Output is correct |
13 |
Correct |
1 ms |
468 KB |
Output is correct |
14 |
Correct |
1 ms |
468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
468 KB |
Output is correct |
3 |
Correct |
1 ms |
468 KB |
Output is correct |
4 |
Correct |
1 ms |
468 KB |
Output is correct |
5 |
Correct |
1 ms |
468 KB |
Output is correct |
6 |
Correct |
1 ms |
468 KB |
Output is correct |
7 |
Correct |
1 ms |
468 KB |
Output is correct |
8 |
Correct |
1 ms |
468 KB |
Output is correct |
9 |
Correct |
1 ms |
468 KB |
Output is correct |
10 |
Correct |
1 ms |
468 KB |
Output is correct |
11 |
Correct |
1 ms |
468 KB |
Output is correct |
12 |
Correct |
1 ms |
456 KB |
Output is correct |
13 |
Correct |
1 ms |
468 KB |
Output is correct |
14 |
Correct |
1 ms |
468 KB |
Output is correct |
15 |
Correct |
1 ms |
464 KB |
Output is correct |
16 |
Correct |
4 ms |
4180 KB |
Output is correct |
17 |
Correct |
6 ms |
4428 KB |
Output is correct |
18 |
Correct |
6 ms |
4436 KB |
Output is correct |
19 |
Correct |
8 ms |
4344 KB |
Output is correct |
20 |
Correct |
7 ms |
3924 KB |
Output is correct |
21 |
Correct |
7 ms |
4564 KB |
Output is correct |
22 |
Correct |
7 ms |
4436 KB |
Output is correct |
23 |
Correct |
6 ms |
4564 KB |
Output is correct |
24 |
Correct |
6 ms |
4084 KB |
Output is correct |
25 |
Correct |
7 ms |
4564 KB |
Output is correct |
26 |
Correct |
6 ms |
4564 KB |
Output is correct |
27 |
Correct |
7 ms |
4564 KB |
Output is correct |
28 |
Correct |
7 ms |
4568 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
468 KB |
Output is correct |
3 |
Correct |
1 ms |
468 KB |
Output is correct |
4 |
Correct |
1 ms |
468 KB |
Output is correct |
5 |
Correct |
1 ms |
468 KB |
Output is correct |
6 |
Correct |
1 ms |
468 KB |
Output is correct |
7 |
Correct |
1 ms |
468 KB |
Output is correct |
8 |
Correct |
1 ms |
468 KB |
Output is correct |
9 |
Correct |
1 ms |
468 KB |
Output is correct |
10 |
Correct |
1 ms |
468 KB |
Output is correct |
11 |
Correct |
1 ms |
468 KB |
Output is correct |
12 |
Correct |
1 ms |
456 KB |
Output is correct |
13 |
Correct |
1 ms |
468 KB |
Output is correct |
14 |
Correct |
1 ms |
468 KB |
Output is correct |
15 |
Correct |
1 ms |
464 KB |
Output is correct |
16 |
Correct |
4 ms |
4180 KB |
Output is correct |
17 |
Correct |
6 ms |
4428 KB |
Output is correct |
18 |
Correct |
6 ms |
4436 KB |
Output is correct |
19 |
Correct |
8 ms |
4344 KB |
Output is correct |
20 |
Correct |
7 ms |
3924 KB |
Output is correct |
21 |
Correct |
7 ms |
4564 KB |
Output is correct |
22 |
Correct |
7 ms |
4436 KB |
Output is correct |
23 |
Correct |
6 ms |
4564 KB |
Output is correct |
24 |
Correct |
6 ms |
4084 KB |
Output is correct |
25 |
Correct |
7 ms |
4564 KB |
Output is correct |
26 |
Correct |
6 ms |
4564 KB |
Output is correct |
27 |
Correct |
7 ms |
4564 KB |
Output is correct |
28 |
Correct |
7 ms |
4568 KB |
Output is correct |
29 |
Correct |
527 ms |
82292 KB |
Output is correct |
30 |
Correct |
574 ms |
84116 KB |
Output is correct |
31 |
Correct |
597 ms |
86352 KB |
Output is correct |
32 |
Correct |
449 ms |
86364 KB |
Output is correct |
33 |
Correct |
431 ms |
75620 KB |
Output is correct |
34 |
Correct |
542 ms |
86472 KB |
Output is correct |
35 |
Correct |
947 ms |
100888 KB |
Output is correct |
36 |
Correct |
838 ms |
96676 KB |
Output is correct |
37 |
Correct |
1077 ms |
102080 KB |
Output is correct |