| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1126340 | I_love_Banu | Maxcomp (info1cup18_maxcomp) | C++20 | 0 ms | 0 KiB |
#include"bits/stdc++.h"
using namespace std;
using ll=long long;
using ld=long double;
using str=string;
template<class T,class U>using P=pair<T,U>;
using pi=P<int,int>;
template<class T>using V=vector<T>;
using vi=V<int>;
using vl=V<ll>;
using vvi=V<vi>;
using vpi=V<pair<int,int>>;
template<class T>int lwb(V<T>&a,T b){return int(lb(all(a),b)-begin(a));}
template<class T>int lwb(T a[],int n,T b){return int(lb(a,a+n,b)-a);}
template<class T>int upb(V<T>&a,T b){return int(ub(all(a),b)-begin(a));}
template<class T>int upb(T a[],int n,T b){return int(ub(a,a+n,b)-a);}
template<class T>ll sum(V<T>&a){return accumulate(all(a),0ll);}
template<class T>ll sum(T a[],int n){return accumulate(a,a+n,0ll);}
template<class T>T MAX(V<T>&a){return *max_element(all(a));}
template<class T>T MAX(T a[],int n){return *max_element(a,a+n);}
template<class T>T MIN(V<T>&a){return *min_element(all(a));}
template<class T>T MIN(T a[],int n){return *min_element(a,a+n);}
template<class T,class U>ifstream&operator>>(istream&in,P<T,U>a){return in>>a.first>>a.second;}
#define sz(x)int(size(x))
#define all(x)begin(x),end(x)
#define lla(x)rbegin(x),rend(x)
#define lb lower_bound
#define ub upper_bound
#define FOR(i,a,b)for(int i=(a);i<(b);i++)
#define F0R(i,a)FOR(i,0,a)
#define ROF(i,a,b)for(int i=(b)-1;(a)<=i;i--)
#define R0F(i,a)ROF(i,0,a)
#define rep(a)F0R(_,a)
#define each(a,x)for(auto&a:x)
#define con const int
con mxN = 1e3 + 3;
ll A[mxN][mxN][2];
ll B[mxN][mxN][2];
ll a[mxN][mxN];
main(){
int N, M;
cin >> N >> M;
F0R(i, N){
F0R(j, M){
cin >> a[i][j];
}
}
fill(A, A + mxN * mxN * 2, LLONG_MAX);
fill(A, A + mxN * mxN * 2, LLONG_MIN);
ll ans = LLONG_MIN;
F0R(i, N){
F0R(j, M){
A[i][j][0] = a[i][j] + 1;
B[i][j][0] = a[i][j] - 1;
if (0 < i){
A[i][j][0] = min(A[i][j][0], A[i - 1][j][0] + 1);
B[i][j][0] = max(B[i][j][0], B[i - 1][j][0] - 1);
}
if (0 < j){
A[i][j][0] = min(A[i][j][0], A[i][j - 1][0] + 1);
B[i][j][0] = max(B[i][j][0], B[i][j - 1][0] - 1);
}
}
R0F(j, M){
A[i][j][1] = a[i][j] + 1;
B[i][j][1] = a[i][j] - 1;
if (0 < i){
A[i][j][1] = min(A[i][j][1], A[i - 1][j][0] + 1);
B[i][j][1] = max(B[i][j][1], B[i - 1][j][0] - 1);
}
if (j < M - 1){
A[i][j][1] = min(A[i][j][1], A[i][j + 1][0] + 1);
B[i][j][1] = max(B[i][j][1], B[i][j + 1][0] - 1);
}
}
F0R(j, M){
ll mn = LLONG_MAX;
if (0 < i){
mn = min({mn, A[i - 1][j][0], A[i - 1][j][1]});
}
if (0 < j){
mn = min(mn, A[i][j - 1][0]);
}
if (j < M - 1){
mn = min(mn, A[i][j + 1][1]);
}
mn ++;
ans = max(ans, a[i][j] - mn);
ll mx = LLONG_MIN;
if (0 < i){
mx = max({mx, B[i - 1][j][0], B[i - 1][j][1]});
}
if (0 < j){
mx = max(mx, B[i][j - 1][0]);
}
if (j < M - 1){
mx = max(mx, B[i][j + 1][1]);
}
mx --;
ans = max(ans, mx - a[i][j]);
}
}
cout << ans << endl;
}