#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 + 1;
const int MOD = 1e9 + 7;
void solve(){
int n , m;
cin>>n>>m;
vector <vector<int>> a(n,vector <int> (m));
int mx = 0;
int mn = INF;
int ans = INF;
for(int i = 0;i < n;i++){
for(int j = 0;j < m;j++){
cin>>a[i][j];
mx = max(mx,a[i][j]);
mn = min(mn,a[i][j]);
}
}
auto check = [&](int m1){
vector <vector<int>> color1(n,vector<int> (m));
vector <vector<int>> color2(n,vector<int> (m));
vector <vector<int>> color3(n,vector<int> (m));
vector <vector<int>> color4(n,vector<int> (m));
for(int i = 0;i < n;i++){
for(int j = 0;j < m;j++){
if(abs(a[i][j] - mx) <= m1){
if(abs(a[i][j] - mn) <= m1){
color1[i][j] = 3;
color2[i][j] = 3;
color3[i][j] = 3;
color4[i][j] = 3;
}
else{
color1[i][j] = 1;
color2[i][j] = 1;
color3[i][j] = 1;
color4[i][j] = 1;
}
}
else if(abs(a[i][j] - mn) <= m1){
color1[i][j] = 2;
color2[i][j] = 2;
color3[i][j] = 2;
color4[i][j] = 2;
}
}
}
if(color1[0][0] == 1){
for(int i =0;i < n;i++){
for(int j = 0;j < m;j++){
if(color1[i][j] == 1){
for(int q = i;q >= 0;q--){
color1[q][j] = 1;
}
for(int q = j;q >= 0;q--){
color1[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(color1[i][j] == 3){
color1[i][j] = 2;
}
if(color1[i][j] == 1){
mx1 = max(mx1,a[i][j]);
mn1 = min(mn1,a[i][j]);
}
else if(color1[i][j] == 2){
mx2 = max(mx2,a[i][j]);
mn2 = min(mn2,a[i][j]);
}
}
}
if((mx1 - mn1 <= m1) && (mx2 - mn2 <= m1)){
ans = min(m1,ans);
return true;
}
}
if(color1[0][0] == 2){
for(int i =0;i < n;i++){
for(int j = 0;j < m;j++){
if(color1[i][j] == 2){
for(int q = i;q >= 0;q--){
color1[q][j] = 2;
}
for(int q = j;q >= 0;q--){
color1[i][q] = 2;
}
}
}
}
int mx1 = 0, mn1 =INF, mx2 = 0,mn2 = INF;
for(int i = 0;i < n;i++){
for(int j = 0;j < m;j++){
if(color1[i][j] == 3){
color1[i][j] = 1;
}
if(color1[i][j] == 1){
mx1 = max(mx1,a[i][j]);
mn1 = min(mn1,a[i][j]);
}
else if(color1[i][j] == 2){
mx2 = max(mx2,a[i][j]);
mn2 = min(mn2,a[i][j]);
}
}
}
if((mx1 - mn1 <= m1) && (mx2 - mn2 <= m1)){
ans = min(m1,ans);
return true;
}
}
if(color2[0][m - 1] == 1){
for(int i =0;i < n;i++){
for(int j = 0;j < m;j++){
if(color2[i][j] == 1){
for(int q = i;q >= 0;q--){
color2[q][j] = 1;
}
for(int q = j;q < m;q++){
color2[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(color2[i][j] == 3){
color2[i][j] = 2;
}
if(color2[i][j] == 1){
mx1 = max(mx1,a[i][j]);
mn1 = min(mn1,a[i][j]);
}
else if(color2[i][j] == 2){
mx2 = max(mx2,a[i][j]);
mn2 = min(mn2,a[i][j]);
}
}
}
if((mx1 - mn1 <= m1) && (mx2 - mn2 <= m1)){
ans = min(ans,m1);
return true;
}
}
if(color2[0][m - 1] == 2){
for(int i =0;i < n;i++){
for(int j = 0;j < m;j++){
if(color2[i][j] == 2){
for(int q = i;q >= 0;q--){
color2[q][j] = 2;
}
for(int q = j;q < m;q++){
color2[i][q] = 2;
}
}
}
}
int mx1 = 0, mn1 =INF, mx2 = 0,mn2 = INF;
for(int i = 0;i < n;i++){
for(int j = 0;j < m;j++){
if(color2[i][j] == 3){
color2[i][j] = 1;
}
if(color2[i][j] == 1){
mx1 = max(mx1,a[i][j]);
mn1 = min(mn1,a[i][j]);
}
else if(color2[i][j] == 2){
mx2 = max(mx2,a[i][j]);
mn2 = min(mn2,a[i][j]);
}
}
}
if((mx1 - mn1 <= m1) && (mx2 - mn2 <= m1)){
ans = min(ans,m1);
return true;
}
}
if(color3[n - 1][0] == 1){
for(int i =0;i < n;i++){
for(int j = 0;j < m;j++){
if(color3[i][j] == 1){
for(int q = i;q < n;q++){
color3[q][j] = 1;
}
for(int q = j;q >= 0;q--){
color3[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(color3[i][j] == 3){
color3[i][j] = 2;
}
if(color3[i][j] == 1){
mx1 = max(mx1,a[i][j]);
mn1 = min(mn1,a[i][j]);
}
else if(color3[i][j] == 2){
mx2 = max(mx2,a[i][j]);
mn2 = min(mn2,a[i][j]);
}
}
}
if((mx1 - mn1 <= m1) && (mx2 - mn2 <= m1)){
ans = min(ans,m1);
return true;
}
}
if(color3[n - 1][0] == 2){
for(int i =0;i < n;i++){
for(int j = 0;j < m;j++){
if(color3[i][j] == 2){
for(int q = i;q < n;q++){
color3[q][j] = 2;
}
for(int q = j;q >= 0;q--){
color3[i][q] = 2;
}
}
}
}
int mx1 = 0, mn1 =INF, mx2 = 0,mn2 = INF;
for(int i = 0;i < n;i++){
for(int j = 0;j < m;j++){
if(color3[i][j] == 3){
color3[i][j] = 1;
}
if(color3[i][j] == 1){
mx1 = max(mx1,a[i][j]);
mn1 = min(mn1,a[i][j]);
}
else if(color3[i][j] == 2){
mx2 = max(mx2,a[i][j]);
mn2 = min(mn2,a[i][j]);
}
}
}
if((mx1 - mn1 <= m1) && (mx2 - mn2 <= m1)){
ans = min(ans,m1);
return true;
}
}
if(color4[n - 1][m - 1] == 1){
for(int i =0;i < n;i++){
for(int j = 0;j < m;j++){
if(color4[i][j] == 1){
for(int q = i;q < n;q++){
color4[q][j] = 1;
}
for(int q = j;q < m;q++){
color4[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(color4[i][j] == 3){
color4[i][j] = 2;
}
if(color4[i][j] == 1){
mx1 = max(mx1,a[i][j]);
mn1 = min(mn1,a[i][j]);
}
else if(color4[i][j] == 2){
mx2 = max(mx2,a[i][j]);
mn2 = min(mn2,a[i][j]);
}
}
}
if((mx1 - mn1 <= m1) && (mx2 - mn2 <= m1)){
ans = min(ans,m1);
return true;
}
}
if(color4[n - 1][m - 1] == 2){
for(int i =0;i < n;i++){
for(int j = 0;j < m;j++){
if(color4[i][j] == 2){
for(int q = i;q < n;q++){
color4[q][j] = 2;
}
for(int q = j;q < m;q++){
color4[i][q] = 2;
}
}
}
}
int mx1 = 0, mn1 =INF, mx2 = 0,mn2 = INF;
for(int i = 0;i < n;i++){
for(int j = 0;j < m;j++){
if(color4[i][j] == 3){
color4[i][j] = 1;
}
if(color4[i][j] == 1){
mx1 = max(mx1,a[i][j]);
mn1 = min(mn1,a[i][j]);
}
else if(color4[i][j] == 2){
mx2 = max(mx2,a[i][j]);
mn2 = min(mn2,a[i][j]);
}
}
}
if((mx1 - mn1 <= m1) && (mx2 - mn2 <= m1)){
ans = min(ans,m1);
return true;
}
}
return false;
};
int l = 0,r = mx - mn;
while(1 < r - l){
int m2 = (l + r) >> 1;
if(check(m2)){
r = m2;
}
else{
l = m2;
}
}
cout<<ans;
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int t = 1;
while (t--) {
solve();
}
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
