#include <bits/stdc++.h>
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;
#define FOR(i,n) for(int i=0;i<n;i++)
#define ROF(i,m,n) for(int i=m;i<=n;i++)
#define vi vector<int>
#define pb push_back
#define alle(a) a.begin(),a.end()
#define rall(n) rbegin(n),rend(n)
#define int long long
#define vecs vector<int>
#define ll long long
#define ss second
#define ff first
const int INF = 1e9;
const int MOD = 1e9 + 7;
void solve(){
int n , m;
cin>>n>>m;
vector <vector<int>> a(n,vector <int> (m));
vector <vector<int>> color(n,vector<int> (m));
int mx = 0;
int mn = INF;
int y1,y2;
int g1,g2;
int ans = 0;
for(int i = 0;i < n;i++){
for(int j = 0;j < m;j++){
cin>>a[i][j];
if(a[i][j] > mx){
mx = a[i][j];
y1 = i;
g1 = j;
}
if(a[i][i] < mn){
mn = a[i][j];
y2 = i;
g2 = j;
}
}
}
color[y1][g1] = 1;
color[y2][g2] = 2;
auto check = [&](int m1){
color[y1][g1] = 1;
color[y2][g2] = 2;
for(int i = 0;i < n;i++){
for(int j = 0;j < m;j++){
if(mx - a[i][j] <= m&& a[i][j] - mn <= m1){
color[i][j] = 3;
}
if(mx - a[i][j] <= m1){
color[i][j] = 1;
}
else if(a[i][j] - mn <= m1){
color[i][j] = 2;
}
}
}
if(color[0][0] == 1||color[0][0] == 3){
for(int i =0;i < n;i++){
for(int j = 0;j < m;j++){
if(color[i][j] == 1){
for(int q = i;q >= 0;q--){
color[q][j] = 1;
}
for(int q = j;q >= 0;q--){
color[i][q] = 1;
}
}
}
}
int mx1 = 0, mn1 =INF, mx2 = 0,mn2 = INF;
for(int i = 0;i < n;i++){
for(int j = 0;j < m;j++){
if(color[i][j] == 3){
color[i][j] = 2;
}
if(color[i][j] == 1){
mx1 = max(mx1,a[i][j]);
mn1 = min(mn1,a[i][j]);
}
else if(color[i][j] == 2){
mx2 = max(mx2,a[i][j]);
mn2 = min(mn2,a[i][j]);
}
}
}
if((mx1 - mn1 <= m1) && (mx2 - mn2 <= m1)){
return true;
}
}
if(color[0][m - 1] == 1||color[0][m - 1] == 3){
for(int i =0;i < n;i++){
for(int j = 0;j < m;j++){
if(color[i][j] == 1){
for(int q = i;q >= 0;q--){
color[q][j] = 1;
}
for(int q = j;q < m;q++){
color[i][q] = 1;
}
}
}
}
int mx1 = 0, mn1 =INF, mx2 = 0,mn2 = INF;
for(int i = 0;i < n;i++){
for(int j = 0;j < m;j++){
if(color[i][j] == 3){
color[i][j] = 2;
}
if(color[i][j] == 1){
mx1 = max(mx1,a[i][j]);
mn1 = min(mn1,a[i][j]);
}
else if(color[i][j] == 2){
mx2 = max(mx2,a[i][j]);
mn2 = min(mn2,a[i][j]);
}
}
}
if((mx1 - mn1 <= m1) && (mx2 - mn2 <= m1)){
return true;
}
}
if(color[n - 1][0] == 1||color[n - 1][0] == 3){
for(int i =0;i < n;i++){
for(int j = 0;j < m;j++){
if(color[i][j] == 1){
for(int q = i;q < n;q++){
color[q][j] = 1;
}
for(int q = j;q >= 0;q--){
color[i][q] = 1;
}
}
}
}
int mx1 = 0, mn1 =INF, mx2 = 0,mn2 = INF;
for(int i = 0;i < n;i++){
for(int j = 0;j < m;j++){
if(color[i][j] == 3){
color[i][j] = 2;
}
if(color[i][j] == 1){
mx1 = max(mx1,a[i][j]);
mn1 = min(mn1,a[i][j]);
}
else if(color[i][j] == 2){
mx2 = max(mx2,a[i][j]);
mn2 = min(mn2,a[i][j]);
}
}
}
if((mx1 - mn1 <= m1) && (mx2 - mn2 <= m1)){
return true;
}
}
if(color[n - 1][m] == 1||color[n - 1][m - 1] == 3){
for(int i =0;i < n;i++){
for(int j = 0;j < m;j++){
if(color[i][j] == 1){
for(int q = i;q < n;q++){
color[q][j] = 1;
}
for(int q = j;q < m;q++){
color[i][q] = 1;
}
}
}
}
int mx1 = 0, mn1 =INF, mx2 = 0,mn2 = INF;
for(int i = 0;i < n;i++){
for(int j = 0;j < m;j++){
if(color[i][j] == 3){
color[i][j] = 2;
}
if(color[i][j] == 1){
mx1 = max(mx1,a[i][j]);
mn1 = min(mn1,a[i][j]);
}
else if(color[i][j] == 2){
mx2 = max(mx2,a[i][j]);
mn2 = min(mn2,a[i][j]);
}
}
}
if((mx1 - mn1 <= m1) && (mx2 - mn2 <= m1)){
return true;
}
}
return false;
};
int l = 0,r = mx - mn + 1;
while(1 < r - l){
int m = (l + r) >> 1;
if(check(m)){
r = m;
}
else{
l = m;
}
}
if(check(l)){
cout<<l;
}
else{
cout<<r;
}
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int t = 1;
while (t--) {
solve();
}
return 0;
}
Compilation message
joioi.cpp: In function 'void solve()':
joioi.cpp:28:9: warning: unused variable 'ans' [-Wunused-variable]
28 | int ans = 0;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
