#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
int N, M, ans;
int gm=1234567890, mx, my;
int A[2020][2020];
int P[2020];
bool chk(int k){
for (int i=1; i<=N; i++) for (P[i]=0; A[i][P[i]+1]-gm<=k && P[i]<M; P[i]++);
int Max=0, Min=1234567890, t=M;
for (int i=1; i<=N; i++){
t = min(t, P[i]);
if (i==mx && t<my){
Max = 1234567890;
Min = 0;
break;
}
for (int j=t+1; j<=M; j++){
Max = max(Max, A[i][j]);
Min = min(Min, A[i][j]);
}
}
if (Max-Min <= k) return true;
Max=0, Min=1234567890, t=M;
for (int i=N; i>=1; i--){
t = min(t, P[i]);
if (i==mx && t<my){
Max = 1234567890;
Min = 0;
break;
}
for (int j=t+1; j<=M; j++){
Max = max(Max, A[i][j]);
Min = min(Min, A[i][j]);
}
}
if (Max-Min <= k) return true;
return false;
}
int main(){
scanf("%d %d", &N, &M);
for (int i=1; i<=N; i++) for (int j=1; j<=M; j++){
scanf("%d", &A[i][j]);
if (gm > A[i][j]) gm = A[i][j], mx = i, my = j;
}
int L=0, H=1'000'000'000;
while (L<=H){
int mid = (L+H)/2;
if (chk(mid)) ans = mid, H = mid-1;
else L = mid+1;
}
L=0, H=ans;
for (int i=1; i<=N; i++) for (int j=1; j<=M/2; j++) swap(A[i][j], A[i][M-j+1]);
my = M-my+1;
while (L<=H){
int mid = (L+H)/2;
if (chk(mid)) ans = mid, H = mid-1;
else L = mid+1;
}
printf("%d\n", ans);
return 0;
}
Compilation message
joioi.cpp: In function 'int main()':
joioi.cpp:46:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &N, &M);
~~~~~^~~~~~~~~~~~~~~~~
joioi.cpp:48:8: 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 |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| 6 |
Correct |
9 ms |
376 KB |
Output is correct |
| 7 |
Correct |
1 ms |
376 KB |
Output is correct |
| 8 |
Correct |
3 ms |
376 KB |
Output is correct |
| 9 |
Correct |
2 ms |
376 KB |
Output is correct |
| 10 |
Correct |
2 ms |
376 KB |
Output is correct |
| 11 |
Correct |
2 ms |
376 KB |
Output is correct |
| 12 |
Correct |
2 ms |
376 KB |
Output is correct |
| 13 |
Correct |
2 ms |
376 KB |
Output is correct |
| 14 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| 6 |
Correct |
9 ms |
376 KB |
Output is correct |
| 7 |
Correct |
1 ms |
376 KB |
Output is correct |
| 8 |
Correct |
3 ms |
376 KB |
Output is correct |
| 9 |
Correct |
2 ms |
376 KB |
Output is correct |
| 10 |
Correct |
2 ms |
376 KB |
Output is correct |
| 11 |
Correct |
2 ms |
376 KB |
Output is correct |
| 12 |
Correct |
2 ms |
376 KB |
Output is correct |
| 13 |
Correct |
2 ms |
376 KB |
Output is correct |
| 14 |
Correct |
2 ms |
376 KB |
Output is correct |
| 15 |
Correct |
3 ms |
376 KB |
Output is correct |
| 16 |
Correct |
8 ms |
1272 KB |
Output is correct |
| 17 |
Correct |
13 ms |
1592 KB |
Output is correct |
| 18 |
Correct |
11 ms |
1528 KB |
Output is correct |
| 19 |
Correct |
12 ms |
1528 KB |
Output is correct |
| 20 |
Correct |
12 ms |
1400 KB |
Output is correct |
| 21 |
Correct |
16 ms |
1656 KB |
Output is correct |
| 22 |
Correct |
13 ms |
1656 KB |
Output is correct |
| 23 |
Correct |
14 ms |
1656 KB |
Output is correct |
| 24 |
Correct |
12 ms |
1532 KB |
Output is correct |
| 25 |
Correct |
14 ms |
1656 KB |
Output is correct |
| 26 |
Correct |
14 ms |
1656 KB |
Output is correct |
| 27 |
Correct |
14 ms |
1656 KB |
Output is correct |
| 28 |
Correct |
17 ms |
1784 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| 6 |
Correct |
9 ms |
376 KB |
Output is correct |
| 7 |
Correct |
1 ms |
376 KB |
Output is correct |
| 8 |
Correct |
3 ms |
376 KB |
Output is correct |
| 9 |
Correct |
2 ms |
376 KB |
Output is correct |
| 10 |
Correct |
2 ms |
376 KB |
Output is correct |
| 11 |
Correct |
2 ms |
376 KB |
Output is correct |
| 12 |
Correct |
2 ms |
376 KB |
Output is correct |
| 13 |
Correct |
2 ms |
376 KB |
Output is correct |
| 14 |
Correct |
2 ms |
376 KB |
Output is correct |
| 15 |
Correct |
3 ms |
376 KB |
Output is correct |
| 16 |
Correct |
8 ms |
1272 KB |
Output is correct |
| 17 |
Correct |
13 ms |
1592 KB |
Output is correct |
| 18 |
Correct |
11 ms |
1528 KB |
Output is correct |
| 19 |
Correct |
12 ms |
1528 KB |
Output is correct |
| 20 |
Correct |
12 ms |
1400 KB |
Output is correct |
| 21 |
Correct |
16 ms |
1656 KB |
Output is correct |
| 22 |
Correct |
13 ms |
1656 KB |
Output is correct |
| 23 |
Correct |
14 ms |
1656 KB |
Output is correct |
| 24 |
Correct |
12 ms |
1532 KB |
Output is correct |
| 25 |
Correct |
14 ms |
1656 KB |
Output is correct |
| 26 |
Correct |
14 ms |
1656 KB |
Output is correct |
| 27 |
Correct |
14 ms |
1656 KB |
Output is correct |
| 28 |
Correct |
17 ms |
1784 KB |
Output is correct |
| 29 |
Correct |
746 ms |
21096 KB |
Output is correct |
| 30 |
Correct |
707 ms |
21752 KB |
Output is correct |
| 31 |
Correct |
747 ms |
22136 KB |
Output is correct |
| 32 |
Correct |
764 ms |
22288 KB |
Output is correct |
| 33 |
Correct |
645 ms |
19904 KB |
Output is correct |
| 34 |
Correct |
757 ms |
22104 KB |
Output is correct |
| 35 |
Correct |
1022 ms |
26248 KB |
Output is correct |
| 36 |
Correct |
900 ms |
24932 KB |
Output is correct |
| 37 |
Correct |
1101 ms |
26204 KB |
Output is correct |
