#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pi;
typedef long long lint;
int n, m, a[2005][2005], mn = 1e9, mx = -1e9;
int a1[2005], a2[2005];
bool ok(int x){
memset(a1, 0, sizeof(a1));
memset(a2, 0x3f, sizeof(a2));
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
if(a[i][j] > mn + x){
a1[i] = max(a1[i], j+1);
}
if(a[i][j] < mx - x){
a2[i] = min(a2[i], j+1);
}
}
}
for(int i=n-1; i>=0; i--){
a1[i] = max(a1[i], a1[i+1]);
}
for(int i=0; i<n; i++){
if(i > 0) a2[i] = min(a2[i], a2[i-1]);
if(a1[i] >= a2[i]) return 0;
}
return 1;
}
int solve(){
int s = 0, e = 1e9;
while(s != e){
int m = (s+e)/2;
if(ok(m)) e = m;
else s = m+1;
}
return s;
}
int main(){
scanf("%d %d",&n,&m);
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
scanf("%d",&a[i][j]);
mn = min(mn, a[i][j]);
mx = max(mx, a[i][j]);
}
}
int ans = solve();
for(int i=0; i<n; i++) reverse(a[i], a[i] + m);
ans = min(ans, solve());
for(int i=0; i<m; i++){
for(int j=0; j<n-1-j; j++){
swap(a[j][i], a[n-1-j][i]);
}
}
ans = min(ans, solve());
for(int i=0; i<n; i++) reverse(a[i], a[i] + m);
ans = min(ans, solve());
cout << ans;
}
Compilation message
joioi.cpp: In function 'int main()':
joioi.cpp:44:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&n,&m);
^
joioi.cpp:47:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&a[i][j]);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
17736 KB |
Output is correct |
| 2 |
Correct |
0 ms |
17736 KB |
Output is correct |
| 3 |
Correct |
0 ms |
17736 KB |
Output is correct |
| 4 |
Correct |
0 ms |
17736 KB |
Output is correct |
| 5 |
Correct |
0 ms |
17736 KB |
Output is correct |
| 6 |
Correct |
0 ms |
17736 KB |
Output is correct |
| 7 |
Correct |
0 ms |
17736 KB |
Output is correct |
| 8 |
Correct |
0 ms |
17736 KB |
Output is correct |
| 9 |
Correct |
0 ms |
17736 KB |
Output is correct |
| 10 |
Correct |
0 ms |
17736 KB |
Output is correct |
| 11 |
Correct |
0 ms |
17736 KB |
Output is correct |
| 12 |
Correct |
0 ms |
17736 KB |
Output is correct |
| 13 |
Correct |
0 ms |
17736 KB |
Output is correct |
| 14 |
Correct |
0 ms |
17736 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
17736 KB |
Output is correct |
| 2 |
Correct |
0 ms |
17736 KB |
Output is correct |
| 3 |
Correct |
0 ms |
17736 KB |
Output is correct |
| 4 |
Correct |
0 ms |
17736 KB |
Output is correct |
| 5 |
Correct |
0 ms |
17736 KB |
Output is correct |
| 6 |
Correct |
0 ms |
17736 KB |
Output is correct |
| 7 |
Correct |
0 ms |
17736 KB |
Output is correct |
| 8 |
Correct |
0 ms |
17736 KB |
Output is correct |
| 9 |
Correct |
0 ms |
17736 KB |
Output is correct |
| 10 |
Correct |
0 ms |
17736 KB |
Output is correct |
| 11 |
Correct |
0 ms |
17736 KB |
Output is correct |
| 12 |
Correct |
0 ms |
17736 KB |
Output is correct |
| 13 |
Correct |
0 ms |
17736 KB |
Output is correct |
| 14 |
Correct |
0 ms |
17736 KB |
Output is correct |
| 15 |
Correct |
0 ms |
17736 KB |
Output is correct |
| 16 |
Correct |
9 ms |
17736 KB |
Output is correct |
| 17 |
Correct |
13 ms |
17736 KB |
Output is correct |
| 18 |
Correct |
13 ms |
17736 KB |
Output is correct |
| 19 |
Correct |
23 ms |
17736 KB |
Output is correct |
| 20 |
Correct |
19 ms |
17736 KB |
Output is correct |
| 21 |
Correct |
19 ms |
17736 KB |
Output is correct |
| 22 |
Correct |
16 ms |
17736 KB |
Output is correct |
| 23 |
Correct |
26 ms |
17736 KB |
Output is correct |
| 24 |
Correct |
13 ms |
17736 KB |
Output is correct |
| 25 |
Correct |
23 ms |
17736 KB |
Output is correct |
| 26 |
Correct |
16 ms |
17736 KB |
Output is correct |
| 27 |
Correct |
16 ms |
17736 KB |
Output is correct |
| 28 |
Correct |
16 ms |
17736 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
17736 KB |
Output is correct |
| 2 |
Correct |
0 ms |
17736 KB |
Output is correct |
| 3 |
Correct |
0 ms |
17736 KB |
Output is correct |
| 4 |
Correct |
0 ms |
17736 KB |
Output is correct |
| 5 |
Correct |
0 ms |
17736 KB |
Output is correct |
| 6 |
Correct |
0 ms |
17736 KB |
Output is correct |
| 7 |
Correct |
0 ms |
17736 KB |
Output is correct |
| 8 |
Correct |
0 ms |
17736 KB |
Output is correct |
| 9 |
Correct |
0 ms |
17736 KB |
Output is correct |
| 10 |
Correct |
0 ms |
17736 KB |
Output is correct |
| 11 |
Correct |
0 ms |
17736 KB |
Output is correct |
| 12 |
Correct |
0 ms |
17736 KB |
Output is correct |
| 13 |
Correct |
0 ms |
17736 KB |
Output is correct |
| 14 |
Correct |
0 ms |
17736 KB |
Output is correct |
| 15 |
Correct |
0 ms |
17736 KB |
Output is correct |
| 16 |
Correct |
9 ms |
17736 KB |
Output is correct |
| 17 |
Correct |
13 ms |
17736 KB |
Output is correct |
| 18 |
Correct |
13 ms |
17736 KB |
Output is correct |
| 19 |
Correct |
23 ms |
17736 KB |
Output is correct |
| 20 |
Correct |
19 ms |
17736 KB |
Output is correct |
| 21 |
Correct |
19 ms |
17736 KB |
Output is correct |
| 22 |
Correct |
16 ms |
17736 KB |
Output is correct |
| 23 |
Correct |
26 ms |
17736 KB |
Output is correct |
| 24 |
Correct |
13 ms |
17736 KB |
Output is correct |
| 25 |
Correct |
23 ms |
17736 KB |
Output is correct |
| 26 |
Correct |
16 ms |
17736 KB |
Output is correct |
| 27 |
Correct |
16 ms |
17736 KB |
Output is correct |
| 28 |
Correct |
16 ms |
17736 KB |
Output is correct |
| 29 |
Correct |
1429 ms |
17736 KB |
Output is correct |
| 30 |
Correct |
1476 ms |
17736 KB |
Output is correct |
| 31 |
Correct |
1636 ms |
17736 KB |
Output is correct |
| 32 |
Correct |
1446 ms |
17736 KB |
Output is correct |
| 33 |
Correct |
1273 ms |
17736 KB |
Output is correct |
| 34 |
Correct |
1629 ms |
17736 KB |
Output is correct |
| 35 |
Correct |
1743 ms |
17736 KB |
Output is correct |
| 36 |
Correct |
1619 ms |
17736 KB |
Output is correct |
| 37 |
Correct |
2086 ms |
17736 KB |
Output is correct |
