#include "bits/stdc++.h"
using namespace std;
const int maxn = 2005;
using ll = long long;
ll a[maxn][maxn], b[maxn][maxn];
int n, m;
ll mn = 1e9, mx = -1e9;
bool can(ll x){
int MX = 0;
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= m; ++j){
if(a[i][j] < mx - x){
MX = max(MX, j);
}
}
for(int j = 1; j <= MX; ++j){
if(a[i][j] > mn + x){
return 0;
}
}
}
return 1;
}
void rotate(){
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= m; ++j){
b[i][j] = a[i][j];
}
}
for(int i = m; i > 0; --i){
for(int j = 1; j <= n; ++j){
a[i][j] = b[j][m - i + 1];
}
}
swap(n, m);
}
int main(int argc, char const *argv[])
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= m; ++j){
cin >> a[i][j];
mn = min(a[i][j], mn);
mx = max(a[i][j], mx);
}
}
ll res = 1e9;
for(int i = 1; i <= 4; ++i){
ll lo = 0, hi = 1e9, ans = -1;
while(lo <= hi){
ll mid = (lo + hi) >> 1;
if(can(mid)){
ans = mid;
hi = mid - 1;
}else {
lo = mid + 1;
}
}
res = min(res, ans);
rotate();
}
cout << res << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
492 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
512 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Correct |
1 ms |
364 KB |
Output is correct |
12 |
Correct |
1 ms |
364 KB |
Output is correct |
13 |
Correct |
1 ms |
364 KB |
Output is correct |
14 |
Correct |
1 ms |
364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
492 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
512 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Correct |
1 ms |
364 KB |
Output is correct |
12 |
Correct |
1 ms |
364 KB |
Output is correct |
13 |
Correct |
1 ms |
364 KB |
Output is correct |
14 |
Correct |
1 ms |
364 KB |
Output is correct |
15 |
Correct |
2 ms |
2028 KB |
Output is correct |
16 |
Correct |
12 ms |
2668 KB |
Output is correct |
17 |
Correct |
13 ms |
2540 KB |
Output is correct |
18 |
Correct |
10 ms |
2560 KB |
Output is correct |
19 |
Correct |
15 ms |
2668 KB |
Output is correct |
20 |
Correct |
10 ms |
2540 KB |
Output is correct |
21 |
Correct |
9 ms |
2540 KB |
Output is correct |
22 |
Correct |
9 ms |
2560 KB |
Output is correct |
23 |
Correct |
10 ms |
2540 KB |
Output is correct |
24 |
Correct |
11 ms |
2540 KB |
Output is correct |
25 |
Correct |
15 ms |
2540 KB |
Output is correct |
26 |
Correct |
10 ms |
2540 KB |
Output is correct |
27 |
Correct |
9 ms |
2540 KB |
Output is correct |
28 |
Correct |
10 ms |
2540 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
492 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
512 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Correct |
1 ms |
364 KB |
Output is correct |
12 |
Correct |
1 ms |
364 KB |
Output is correct |
13 |
Correct |
1 ms |
364 KB |
Output is correct |
14 |
Correct |
1 ms |
364 KB |
Output is correct |
15 |
Correct |
2 ms |
2028 KB |
Output is correct |
16 |
Correct |
12 ms |
2668 KB |
Output is correct |
17 |
Correct |
13 ms |
2540 KB |
Output is correct |
18 |
Correct |
10 ms |
2560 KB |
Output is correct |
19 |
Correct |
15 ms |
2668 KB |
Output is correct |
20 |
Correct |
10 ms |
2540 KB |
Output is correct |
21 |
Correct |
9 ms |
2540 KB |
Output is correct |
22 |
Correct |
9 ms |
2560 KB |
Output is correct |
23 |
Correct |
10 ms |
2540 KB |
Output is correct |
24 |
Correct |
11 ms |
2540 KB |
Output is correct |
25 |
Correct |
15 ms |
2540 KB |
Output is correct |
26 |
Correct |
10 ms |
2540 KB |
Output is correct |
27 |
Correct |
9 ms |
2540 KB |
Output is correct |
28 |
Correct |
10 ms |
2540 KB |
Output is correct |
29 |
Correct |
913 ms |
63340 KB |
Output is correct |
30 |
Correct |
944 ms |
63212 KB |
Output is correct |
31 |
Correct |
1040 ms |
63124 KB |
Output is correct |
32 |
Correct |
1018 ms |
63468 KB |
Output is correct |
33 |
Correct |
838 ms |
62828 KB |
Output is correct |
34 |
Correct |
1020 ms |
63172 KB |
Output is correct |
35 |
Correct |
963 ms |
63312 KB |
Output is correct |
36 |
Correct |
855 ms |
62716 KB |
Output is correct |
37 |
Correct |
1006 ms |
63212 KB |
Output is correct |