#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pp;
void read(int& x){ scanf("%d",&x); }
template<typename T,typename... Args>
void read(T& a,Args&... b){ read(a); read(b...); }
#define all(x) (x).begin(),(x).end()
#define pb push_back
int arr[4][2010][2010];
int N[4], M[4];
void rot(){
for(int d=1; d<4; ++d){
N[d] = M[d-1]; M[d] = N[d-1];
for(int i=1; i<=M[d]; ++i) for(int j=1; j<=N[d]; ++j)
arr[d][N[d]+1-j][i]=arr[d-1][i][j];
}
}
bool can_cur(int d, int x){
static int Mx=-1e9, mn=1e9;
int n = N[d], m = M[d];
if(Mx == int(-1e9)){
for(int i=1; i<=n; ++i){
for(int j=1; j<=m; ++j){
Mx = max(Mx, arr[d][i][j]);
mn = min(mn, arr[d][i][j]);
}
}
}
int ijou = Mx-x;
int ika = x+mn;
int last_max = m+1;
for(int i=1; i<=n; ++i){
int lb=0, rb=m+1;
while(lb<m && arr[d][i][lb+1]>=ijou) ++lb;
while(1<rb && arr[d][i][rb-1]<=ika) --rb;
if(lb+1<rb) return 0;
if(last_max < rb-1) return 0;
last_max = min(last_max, lb);
}
return 1;
}
bool can(int x){
bool ret=0;
for(int i=0; i<4; ++i) if(can_cur(i, x)) return 1;
return 0;
}
int main()
{
read(N[0], M[0]);
for(int i=1; i<=N[0]; ++i) for(int j=1; j<=M[0]; ++j) read(arr[0][i][j]);
rot();
int l=0, r=int(1e9)+10;
while(l+1 < r){
int mid=(l+r)/2;
if(can(mid)) r=mid;
else l=mid;
}
printf("%d\n", r);
return 0;
}
Compilation message
joioi.cpp: In function 'bool can(int)':
joioi.cpp:48:7: warning: unused variable 'ret' [-Wunused-variable]
48 | bool ret=0;
| ^~~
joioi.cpp: In function 'void read(int&)':
joioi.cpp:5:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
5 | void read(int& x){ scanf("%d",&x); }
| ~~~~~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
512 KB |
Output is correct |
| 4 |
Correct |
1 ms |
512 KB |
Output is correct |
| 5 |
Correct |
0 ms |
512 KB |
Output is correct |
| 6 |
Correct |
1 ms |
512 KB |
Output is correct |
| 7 |
Correct |
1 ms |
512 KB |
Output is correct |
| 8 |
Correct |
1 ms |
512 KB |
Output is correct |
| 9 |
Correct |
1 ms |
512 KB |
Output is correct |
| 10 |
Correct |
1 ms |
512 KB |
Output is correct |
| 11 |
Correct |
1 ms |
512 KB |
Output is correct |
| 12 |
Correct |
1 ms |
640 KB |
Output is correct |
| 13 |
Correct |
1 ms |
512 KB |
Output is correct |
| 14 |
Correct |
1 ms |
512 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
512 KB |
Output is correct |
| 4 |
Correct |
1 ms |
512 KB |
Output is correct |
| 5 |
Correct |
0 ms |
512 KB |
Output is correct |
| 6 |
Correct |
1 ms |
512 KB |
Output is correct |
| 7 |
Correct |
1 ms |
512 KB |
Output is correct |
| 8 |
Correct |
1 ms |
512 KB |
Output is correct |
| 9 |
Correct |
1 ms |
512 KB |
Output is correct |
| 10 |
Correct |
1 ms |
512 KB |
Output is correct |
| 11 |
Correct |
1 ms |
512 KB |
Output is correct |
| 12 |
Correct |
1 ms |
640 KB |
Output is correct |
| 13 |
Correct |
1 ms |
512 KB |
Output is correct |
| 14 |
Correct |
1 ms |
512 KB |
Output is correct |
| 15 |
Correct |
2 ms |
2048 KB |
Output is correct |
| 16 |
Correct |
9 ms |
4096 KB |
Output is correct |
| 17 |
Correct |
10 ms |
4480 KB |
Output is correct |
| 18 |
Correct |
9 ms |
4352 KB |
Output is correct |
| 19 |
Correct |
9 ms |
4480 KB |
Output is correct |
| 20 |
Correct |
9 ms |
4096 KB |
Output is correct |
| 21 |
Correct |
12 ms |
4608 KB |
Output is correct |
| 22 |
Correct |
10 ms |
4480 KB |
Output is correct |
| 23 |
Correct |
10 ms |
4480 KB |
Output is correct |
| 24 |
Correct |
10 ms |
4224 KB |
Output is correct |
| 25 |
Correct |
11 ms |
4480 KB |
Output is correct |
| 26 |
Correct |
11 ms |
4608 KB |
Output is correct |
| 27 |
Correct |
12 ms |
4608 KB |
Output is correct |
| 28 |
Correct |
14 ms |
4608 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
512 KB |
Output is correct |
| 4 |
Correct |
1 ms |
512 KB |
Output is correct |
| 5 |
Correct |
0 ms |
512 KB |
Output is correct |
| 6 |
Correct |
1 ms |
512 KB |
Output is correct |
| 7 |
Correct |
1 ms |
512 KB |
Output is correct |
| 8 |
Correct |
1 ms |
512 KB |
Output is correct |
| 9 |
Correct |
1 ms |
512 KB |
Output is correct |
| 10 |
Correct |
1 ms |
512 KB |
Output is correct |
| 11 |
Correct |
1 ms |
512 KB |
Output is correct |
| 12 |
Correct |
1 ms |
640 KB |
Output is correct |
| 13 |
Correct |
1 ms |
512 KB |
Output is correct |
| 14 |
Correct |
1 ms |
512 KB |
Output is correct |
| 15 |
Correct |
2 ms |
2048 KB |
Output is correct |
| 16 |
Correct |
9 ms |
4096 KB |
Output is correct |
| 17 |
Correct |
10 ms |
4480 KB |
Output is correct |
| 18 |
Correct |
9 ms |
4352 KB |
Output is correct |
| 19 |
Correct |
9 ms |
4480 KB |
Output is correct |
| 20 |
Correct |
9 ms |
4096 KB |
Output is correct |
| 21 |
Correct |
12 ms |
4608 KB |
Output is correct |
| 22 |
Correct |
10 ms |
4480 KB |
Output is correct |
| 23 |
Correct |
10 ms |
4480 KB |
Output is correct |
| 24 |
Correct |
10 ms |
4224 KB |
Output is correct |
| 25 |
Correct |
11 ms |
4480 KB |
Output is correct |
| 26 |
Correct |
11 ms |
4608 KB |
Output is correct |
| 27 |
Correct |
12 ms |
4608 KB |
Output is correct |
| 28 |
Correct |
14 ms |
4608 KB |
Output is correct |
| 29 |
Correct |
742 ms |
83868 KB |
Output is correct |
| 30 |
Correct |
705 ms |
82552 KB |
Output is correct |
| 31 |
Correct |
791 ms |
86640 KB |
Output is correct |
| 32 |
Correct |
861 ms |
86416 KB |
Output is correct |
| 33 |
Correct |
691 ms |
79428 KB |
Output is correct |
| 34 |
Correct |
872 ms |
86636 KB |
Output is correct |
| 35 |
Correct |
997 ms |
102064 KB |
Output is correct |
| 36 |
Correct |
847 ms |
92944 KB |
Output is correct |
| 37 |
Correct |
942 ms |
102120 KB |
Output is correct |
