#include <bits/stdc++.h>
using namespace std;
const int DIM = 2005;
int mat[DIM][DIM];
void revLin(int n, int m) {
for (int i = 1; i <= n / 2; ++i) {
for (int j = 1; j <= m; ++j) {
swap(mat[i][j], mat[n - i + 1][j]); } } }
void revCol(int n, int m) {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m / 2; ++j) {
swap(mat[i][j], mat[i][m - j + 1]); } } }
bool check(int n, int m, int vl, int mn, int mx) {
int ps = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (mat[i][j] < mx - vl) {
ps = max(ps, j); } }
for (int j = 1; j <= m; ++j) {
if (mat[i][j] > mn + vl and j <= ps) {
return false; } } }
return true; }
int solve(int n, int m, int mn, int mx) {
int le = 0, ri = mx - mn;
while (le <= ri) {
int md = (le + ri) / 2;
if (check(n, m, md, mn, mx)) {
ri = md - 1; }
else {
le = md + 1; } }
return le; }
int main(void) {
#ifdef HOME
freopen("joioi.in", "r", stdin);
freopen("joioi.out", "w", stdout);
#endif
int n, m, mn = 1000000000, mx = 0; cin >> n >> m;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
cin >> mat[i][j];
mn = min(mn, mat[i][j]); mx = max(mx, mat[i][j]); } }
int ans = 1000000000;
ans = min(ans, solve(n, m, mn, mx)); revLin(n, m);
ans = min(ans, solve(n, m, mn, mx)); revCol(n, m);
ans = min(ans, solve(n, m, mn, mx)); revLin(n, m);
ans = min(ans, solve(n, m, mn, mx)); revCol(n, m);
cout << ans << endl;
return 0; }
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
604 KB |
Output is correct |
3 |
Correct |
2 ms |
604 KB |
Output is correct |
4 |
Correct |
2 ms |
740 KB |
Output is correct |
5 |
Correct |
2 ms |
740 KB |
Output is correct |
6 |
Correct |
2 ms |
744 KB |
Output is correct |
7 |
Correct |
2 ms |
744 KB |
Output is correct |
8 |
Correct |
2 ms |
752 KB |
Output is correct |
9 |
Correct |
2 ms |
796 KB |
Output is correct |
10 |
Correct |
3 ms |
804 KB |
Output is correct |
11 |
Correct |
2 ms |
812 KB |
Output is correct |
12 |
Correct |
2 ms |
816 KB |
Output is correct |
13 |
Correct |
2 ms |
820 KB |
Output is correct |
14 |
Correct |
2 ms |
820 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
604 KB |
Output is correct |
3 |
Correct |
2 ms |
604 KB |
Output is correct |
4 |
Correct |
2 ms |
740 KB |
Output is correct |
5 |
Correct |
2 ms |
740 KB |
Output is correct |
6 |
Correct |
2 ms |
744 KB |
Output is correct |
7 |
Correct |
2 ms |
744 KB |
Output is correct |
8 |
Correct |
2 ms |
752 KB |
Output is correct |
9 |
Correct |
2 ms |
796 KB |
Output is correct |
10 |
Correct |
3 ms |
804 KB |
Output is correct |
11 |
Correct |
2 ms |
812 KB |
Output is correct |
12 |
Correct |
2 ms |
816 KB |
Output is correct |
13 |
Correct |
2 ms |
820 KB |
Output is correct |
14 |
Correct |
2 ms |
820 KB |
Output is correct |
15 |
Correct |
5 ms |
828 KB |
Output is correct |
16 |
Correct |
10 ms |
1860 KB |
Output is correct |
17 |
Correct |
21 ms |
2124 KB |
Output is correct |
18 |
Correct |
22 ms |
2396 KB |
Output is correct |
19 |
Correct |
24 ms |
2664 KB |
Output is correct |
20 |
Correct |
20 ms |
2824 KB |
Output is correct |
21 |
Correct |
27 ms |
3448 KB |
Output is correct |
22 |
Correct |
28 ms |
3776 KB |
Output is correct |
23 |
Correct |
31 ms |
4092 KB |
Output is correct |
24 |
Correct |
26 ms |
4388 KB |
Output is correct |
25 |
Correct |
34 ms |
4908 KB |
Output is correct |
26 |
Correct |
29 ms |
5248 KB |
Output is correct |
27 |
Correct |
27 ms |
5636 KB |
Output is correct |
28 |
Correct |
27 ms |
6024 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
604 KB |
Output is correct |
3 |
Correct |
2 ms |
604 KB |
Output is correct |
4 |
Correct |
2 ms |
740 KB |
Output is correct |
5 |
Correct |
2 ms |
740 KB |
Output is correct |
6 |
Correct |
2 ms |
744 KB |
Output is correct |
7 |
Correct |
2 ms |
744 KB |
Output is correct |
8 |
Correct |
2 ms |
752 KB |
Output is correct |
9 |
Correct |
2 ms |
796 KB |
Output is correct |
10 |
Correct |
3 ms |
804 KB |
Output is correct |
11 |
Correct |
2 ms |
812 KB |
Output is correct |
12 |
Correct |
2 ms |
816 KB |
Output is correct |
13 |
Correct |
2 ms |
820 KB |
Output is correct |
14 |
Correct |
2 ms |
820 KB |
Output is correct |
15 |
Correct |
5 ms |
828 KB |
Output is correct |
16 |
Correct |
10 ms |
1860 KB |
Output is correct |
17 |
Correct |
21 ms |
2124 KB |
Output is correct |
18 |
Correct |
22 ms |
2396 KB |
Output is correct |
19 |
Correct |
24 ms |
2664 KB |
Output is correct |
20 |
Correct |
20 ms |
2824 KB |
Output is correct |
21 |
Correct |
27 ms |
3448 KB |
Output is correct |
22 |
Correct |
28 ms |
3776 KB |
Output is correct |
23 |
Correct |
31 ms |
4092 KB |
Output is correct |
24 |
Correct |
26 ms |
4388 KB |
Output is correct |
25 |
Correct |
34 ms |
4908 KB |
Output is correct |
26 |
Correct |
29 ms |
5248 KB |
Output is correct |
27 |
Correct |
27 ms |
5636 KB |
Output is correct |
28 |
Correct |
27 ms |
6024 KB |
Output is correct |
29 |
Correct |
1489 ms |
42364 KB |
Output is correct |
30 |
Correct |
1489 ms |
64552 KB |
Output is correct |
31 |
Correct |
1701 ms |
87644 KB |
Output is correct |
32 |
Correct |
1490 ms |
110948 KB |
Output is correct |
33 |
Correct |
1346 ms |
129048 KB |
Output is correct |
34 |
Correct |
1630 ms |
154084 KB |
Output is correct |
35 |
Correct |
2435 ms |
191712 KB |
Output is correct |
36 |
Correct |
2094 ms |
223948 KB |
Output is correct |
37 |
Correct |
2643 ms |
261336 KB |
Output is correct |