#include <iostream>
using namespace std;
typedef long long ll;
const int MAXN = 2001;
int n, m;
ll tablica[MAXN][MAXN];
ll p1[MAXN][MAXN];
ll wynik = 1000000000000;
ll min_ele = 10000000000000;
void obroc() {
for (int i = 0; n > i; i++) {
for (int j = 0; m > j; j++) {
p1[m - 1 - j][i] = tablica[i][j];
}
}
for (int i = 0; n > i; i++) {
for (int j = 0; m > j; j++) {
tablica[m - 1 -j][i] = p1[m - 1 - j][i];
}
}
swap(m, n);
}
bool BS(ll val) {
int aktl_koniec = 1000000000;
int p1;
ll max_r = -1000000000, min_r = 1000000000;
for (int i = 0; n > i; i++) {
p1 = -1;
while (((p1 + 1) < m) && (tablica[i][p1 + 1] - min_ele) <= val && (aktl_koniec >= p1 + 1)) {
p1++;
}
aktl_koniec = p1;
for (int j = (p1 + 1); m > j; j++) {
max_r = max(max_r, tablica[i][j]);
min_r = min(min_r, tablica[i][j]);
}
}
if ((max_r - min_r) <= val) {
return true;
}
return false;
}
ll zrob_BS() {
ll l = 0, r = 1000000001, mid;
while (r > l) {
mid = (l + r)/2;
if (BS(mid)) {
r = mid;
} else {
l = mid + 1;
}
}
return r;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i = 0; n > i; i++) {
for (int j = 0; m > j; j++) {
cin >> tablica[i][j];
min_ele = min(min_ele, tablica[i][j]);
}
}
wynik = zrob_BS();
for (int i = 0; 3 > i; i++) {
obroc();
wynik = min(wynik, zrob_BS());
}
cout << wynik;
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 6 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 7 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 8 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 9 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 10 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 11 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 12 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 13 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 14 |
Correct |
1 ms |
2384 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 6 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 7 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 8 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 9 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 10 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 11 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 12 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 13 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 14 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 15 |
Correct |
2 ms |
8528 KB |
Output is correct |
| 16 |
Correct |
8 ms |
8784 KB |
Output is correct |
| 17 |
Correct |
9 ms |
8784 KB |
Output is correct |
| 18 |
Correct |
8 ms |
8784 KB |
Output is correct |
| 19 |
Correct |
8 ms |
8784 KB |
Output is correct |
| 20 |
Correct |
8 ms |
8908 KB |
Output is correct |
| 21 |
Correct |
10 ms |
9208 KB |
Output is correct |
| 22 |
Correct |
9 ms |
9040 KB |
Output is correct |
| 23 |
Correct |
9 ms |
9040 KB |
Output is correct |
| 24 |
Correct |
8 ms |
9040 KB |
Output is correct |
| 25 |
Correct |
9 ms |
9040 KB |
Output is correct |
| 26 |
Correct |
9 ms |
9124 KB |
Output is correct |
| 27 |
Correct |
10 ms |
9040 KB |
Output is correct |
| 28 |
Correct |
9 ms |
9132 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 6 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 7 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 8 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 9 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 10 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 11 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 12 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 13 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 14 |
Correct |
1 ms |
2384 KB |
Output is correct |
| 15 |
Correct |
2 ms |
8528 KB |
Output is correct |
| 16 |
Correct |
8 ms |
8784 KB |
Output is correct |
| 17 |
Correct |
9 ms |
8784 KB |
Output is correct |
| 18 |
Correct |
8 ms |
8784 KB |
Output is correct |
| 19 |
Correct |
8 ms |
8784 KB |
Output is correct |
| 20 |
Correct |
8 ms |
8908 KB |
Output is correct |
| 21 |
Correct |
10 ms |
9208 KB |
Output is correct |
| 22 |
Correct |
9 ms |
9040 KB |
Output is correct |
| 23 |
Correct |
9 ms |
9040 KB |
Output is correct |
| 24 |
Correct |
8 ms |
9040 KB |
Output is correct |
| 25 |
Correct |
9 ms |
9040 KB |
Output is correct |
| 26 |
Correct |
9 ms |
9124 KB |
Output is correct |
| 27 |
Correct |
10 ms |
9040 KB |
Output is correct |
| 28 |
Correct |
9 ms |
9132 KB |
Output is correct |
| 29 |
Correct |
663 ms |
85096 KB |
Output is correct |
| 30 |
Correct |
635 ms |
84556 KB |
Output is correct |
| 31 |
Correct |
667 ms |
86208 KB |
Output is correct |
| 32 |
Correct |
656 ms |
86152 KB |
Output is correct |
| 33 |
Correct |
614 ms |
82760 KB |
Output is correct |
| 34 |
Correct |
714 ms |
83904 KB |
Output is correct |
| 35 |
Correct |
712 ms |
101572 KB |
Output is correct |
| 36 |
Correct |
731 ms |
96332 KB |
Output is correct |
| 37 |
Correct |
713 ms |
101840 KB |
Output is correct |
