#include<bits/stdc++.h>
using namespace std;
const int inf = 1e9;
int n,m,pos[2005];
int a[2005][2005],ans = inf,mn = inf,mini[2005][2005],maxi[2005][2005],temp[2005][2005];
void _rotate(){
int numi=1,numj=1;
for(int i = 1 ; i <= m;i++){
for(int j = n;j >= 1;j--){
temp[numi][numj] = a[j][i];
numj++;
}
numj=1;
numi++;
}
swap(n,m);
for(int i = 1;i<=n;i++){
for(int j = 1;j<=m;j++)
a[i][j] = temp[i][j];
}
}
bool check(int val){
for(int i = 1;i <= n;i++){
pos[i] = m + 1;
for(int j = 1;j <= m;j++){
if(a[i][j] > mn + val){pos[i] = j; break;}
}
}
for(int i = 1;i <= n;i++){
mini[i][m+1] = inf;
maxi[i][m+1] = 1;
for(int j = m;j >= 1;j--){
mini[i][j] = min(a[i][j],mini[i][j+1]);
maxi[i][j] = max(a[i][j],maxi[i][j+1]);
}
mini[i][0] = mini[i][1]; maxi[i][0] = maxi[i][1];
}
int curMin = inf,curMax = 1,cur = m+1;
for(int i = 1;i <= n;i++){
cur = min(cur,pos[i]);
curMin = min(curMin,mini[i][cur]);
curMax = max(curMax,maxi[i][cur]);
}
if(curMax - curMin<=val)
return 1;
else
return 0;
}
void solve(){
int l = 0,r = inf - 1,mid;
while(l<r){
mid = (l+r)/2;
if(check(mid)) r = mid;
else l = mid+1;
}
ans = min(ans,l);
}
int main(){
cin.tie(0),ios::sync_with_stdio(0);
cin >> n >> m;
for(int i = 1;i <= n;i++){
for(int j = 1;j <= m;j++){
cin >> a[i][j];
mn = min(mn,a[i][j]);
}
}
solve();
for(int i = 1;i <= 3;i++){
_rotate();
solve();
}
cout << ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
380 KB |
Output is correct |
2 |
Correct |
2 ms |
484 KB |
Output is correct |
3 |
Correct |
2 ms |
688 KB |
Output is correct |
4 |
Correct |
2 ms |
688 KB |
Output is correct |
5 |
Correct |
2 ms |
688 KB |
Output is correct |
6 |
Correct |
2 ms |
688 KB |
Output is correct |
7 |
Correct |
2 ms |
688 KB |
Output is correct |
8 |
Correct |
2 ms |
692 KB |
Output is correct |
9 |
Correct |
2 ms |
692 KB |
Output is correct |
10 |
Correct |
2 ms |
692 KB |
Output is correct |
11 |
Correct |
2 ms |
748 KB |
Output is correct |
12 |
Correct |
2 ms |
748 KB |
Output is correct |
13 |
Correct |
2 ms |
876 KB |
Output is correct |
14 |
Correct |
2 ms |
876 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
380 KB |
Output is correct |
2 |
Correct |
2 ms |
484 KB |
Output is correct |
3 |
Correct |
2 ms |
688 KB |
Output is correct |
4 |
Correct |
2 ms |
688 KB |
Output is correct |
5 |
Correct |
2 ms |
688 KB |
Output is correct |
6 |
Correct |
2 ms |
688 KB |
Output is correct |
7 |
Correct |
2 ms |
688 KB |
Output is correct |
8 |
Correct |
2 ms |
692 KB |
Output is correct |
9 |
Correct |
2 ms |
692 KB |
Output is correct |
10 |
Correct |
2 ms |
692 KB |
Output is correct |
11 |
Correct |
2 ms |
748 KB |
Output is correct |
12 |
Correct |
2 ms |
748 KB |
Output is correct |
13 |
Correct |
2 ms |
876 KB |
Output is correct |
14 |
Correct |
2 ms |
876 KB |
Output is correct |
15 |
Correct |
5 ms |
3836 KB |
Output is correct |
16 |
Correct |
21 ms |
4476 KB |
Output is correct |
17 |
Correct |
25 ms |
4492 KB |
Output is correct |
18 |
Correct |
24 ms |
4492 KB |
Output is correct |
19 |
Correct |
25 ms |
4492 KB |
Output is correct |
20 |
Correct |
22 ms |
4492 KB |
Output is correct |
21 |
Correct |
25 ms |
4492 KB |
Output is correct |
22 |
Correct |
25 ms |
4492 KB |
Output is correct |
23 |
Correct |
24 ms |
4492 KB |
Output is correct |
24 |
Correct |
22 ms |
4492 KB |
Output is correct |
25 |
Correct |
24 ms |
4492 KB |
Output is correct |
26 |
Correct |
24 ms |
4492 KB |
Output is correct |
27 |
Correct |
25 ms |
4492 KB |
Output is correct |
28 |
Correct |
25 ms |
4492 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
380 KB |
Output is correct |
2 |
Correct |
2 ms |
484 KB |
Output is correct |
3 |
Correct |
2 ms |
688 KB |
Output is correct |
4 |
Correct |
2 ms |
688 KB |
Output is correct |
5 |
Correct |
2 ms |
688 KB |
Output is correct |
6 |
Correct |
2 ms |
688 KB |
Output is correct |
7 |
Correct |
2 ms |
688 KB |
Output is correct |
8 |
Correct |
2 ms |
692 KB |
Output is correct |
9 |
Correct |
2 ms |
692 KB |
Output is correct |
10 |
Correct |
2 ms |
692 KB |
Output is correct |
11 |
Correct |
2 ms |
748 KB |
Output is correct |
12 |
Correct |
2 ms |
748 KB |
Output is correct |
13 |
Correct |
2 ms |
876 KB |
Output is correct |
14 |
Correct |
2 ms |
876 KB |
Output is correct |
15 |
Correct |
5 ms |
3836 KB |
Output is correct |
16 |
Correct |
21 ms |
4476 KB |
Output is correct |
17 |
Correct |
25 ms |
4492 KB |
Output is correct |
18 |
Correct |
24 ms |
4492 KB |
Output is correct |
19 |
Correct |
25 ms |
4492 KB |
Output is correct |
20 |
Correct |
22 ms |
4492 KB |
Output is correct |
21 |
Correct |
25 ms |
4492 KB |
Output is correct |
22 |
Correct |
25 ms |
4492 KB |
Output is correct |
23 |
Correct |
24 ms |
4492 KB |
Output is correct |
24 |
Correct |
22 ms |
4492 KB |
Output is correct |
25 |
Correct |
24 ms |
4492 KB |
Output is correct |
26 |
Correct |
24 ms |
4492 KB |
Output is correct |
27 |
Correct |
25 ms |
4492 KB |
Output is correct |
28 |
Correct |
25 ms |
4492 KB |
Output is correct |
29 |
Correct |
2272 ms |
63548 KB |
Output is correct |
30 |
Correct |
2135 ms |
63548 KB |
Output is correct |
31 |
Correct |
2330 ms |
63548 KB |
Output is correct |
32 |
Correct |
2299 ms |
63564 KB |
Output is correct |
33 |
Correct |
2092 ms |
63564 KB |
Output is correct |
34 |
Correct |
2506 ms |
63644 KB |
Output is correct |
35 |
Correct |
2544 ms |
63644 KB |
Output is correct |
36 |
Correct |
2071 ms |
63644 KB |
Output is correct |
37 |
Correct |
2357 ms |
63644 KB |
Output is correct |