#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <utility>
#include <queue>
#include <map>
#include <array>
#include <iomanip>
#include <fstream>
#include <cstdlib>
using namespace std;
vector<vector<int> >A;
vector<int>a;
vector<int>b;
vector<vector<int> >val;
vector<vector<int> >lo;
vector<vector<int> >hi;
int ans;
int m,n;
void actualizar(vector<vector<pair<int,int> > >&con,int a,int b,vector<bool>&vi){
vi[a*m+b]=true;
for(pair<int,int> c:con[a*m+b]){
int x=c.first;
int y=c.second;
if(!vi[x*m+y]){
int h=max(A[x][y],hi[a][b]);
int l=min(A[x][y],lo[a][b]);
int v=val[a][b]-hi[a][b]+lo[a][b]+h-l;
if(v>val[x][y]){
ans=max(ans,v);
val[x][y]=v;
lo[x][y]=l;
hi[x][y]=h;
actualizar(con,x,y,vi);
}
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
int n,m;
cin>>n>>m;
A.resize(n);
a.assign(m,-1);
val.resize(n);
lo.resize(n);
hi.resize(n);
for(int i=0;i<n;i++){
val[i]=a;
hi[i]=a;
lo[i]=a;
}
for(int i=0;i<n;i++)A[i]=a;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>A[i][j];
hi[i][j]=A[i][j];
lo[i][j]=A[i][j];
}
}
ans=-1;
vector<vector<pair<int,int> > >con(n*m);
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(i!=0){
int v=val[i-1][j]-hi[i-1][j]+lo[i-1][j]-1;
int h=max(A[i][j],hi[i-1][j]);
int l=min(A[i][j],lo[i-1][j]);
v+=h;
v-=l;
if(v>val[i][j]){
val[i][j]=v;
hi[i][j]=h;
lo[i][j]=l;
con[i*m+j].push_back(make_pair(i-1,j));
}
if(v>val[i-1][j]){
val[i-1][j]=v;
hi[i-1][j]=h;
lo[i-1][j]=l;
con[(i-1)*m+j].push_back(make_pair(i,j));
vector<bool>vi(n*m,false);
actualizar(con,i-1,j,vi);
}
h=max(A[i][j],A[i-1][j]);
l=min(A[i][j],A[i-1][j]);
v=h-l-2;
if(v>val[i][j]){
val[i][j]=v;
hi[i][j]=h;
lo[i][j]=l;
con[i*m+j].push_back(make_pair(i-1,j));
}
if(v>val[i-1][j]){
val[i-1][j]=v;
hi[i-1][j]=h;
lo[i-1][j]=l;
con[(i-1)*m+j].push_back(make_pair(i,j));
vector<bool>vi(n*m,false);
actualizar(con,i-1,j,vi);
}
}
if(j!=0){
int v=val[i][j-1]-hi[i][j-1]+lo[i][j-1]-1;
int h=max(A[i][j],hi[i][j-1]);
int l=min(A[i][j],lo[i][j-1]);
v+=h;
v-=l;
if(v>val[i][j]){
val[i][j]=v;
hi[i][j]=h;
lo[i][j]=l;
con[i*m+j].push_back(make_pair(i,j-1));
}
if(v>val[i][j-1]){
val[i][j-1]=v;
hi[i][j-1]=h;
lo[i][j-1]=l;
con[(i)*m+j-1].push_back(make_pair(i,j));
vector<bool>vi(n*m,false);
actualizar(con,i,j-1,vi);
}
h=max(A[i][j],A[i][j-1]);
l=min(A[i][j],A[i][j-1]);
v=h-l-2;
if(v>val[i][j]){
val[i][j]=v;
hi[i][j]=h;
lo[i][j]=l;
con[i*m+j].push_back(make_pair(i,j-1));
}
if(v>val[i][j-1]){
val[i][j-1]=v;
hi[i][j-1]=h;
lo[i][j-1]=l;
con[(i)*m+j-1].push_back(make_pair(i,j));
vector<bool>vi(n*m,false);
actualizar(con,i,j-1,vi);
}
}
ans=max(ans,val[i][j]);
}
}
for(int i=n-1;i>0;i--){
for(int j=m-1;j>0;j--){
if(i!=n-1){
int v=val[i+1][j]-hi[i+1][j]+lo[i+1][j]-1;
int h=max(A[i][j],hi[i+1][j]);
int l=min(A[i][j],lo[i+1][j]);
v+=h;
v-=l;
if(v>val[i][j]){
val[i][j]=v;
hi[i][j]=h;
lo[i][j]=l;
con[i*m+j].push_back(make_pair(i+1,j));
}
if(v>val[i+1][j]){
val[i+1][j]=v;
hi[i+1][j]=h;
lo[i+1][j]=l;
con[(i+1)*m+j].push_back(make_pair(i,j));
vector<bool>vi(n*m,false);
actualizar(con,i+1,j,vi);
}
h=max(A[i][j],A[i+1][j]);
l=min(A[i][j],A[i+1][j]);
v=h-l-2;
if(v>val[i][j]){
val[i][j]=v;
hi[i][j]=h;
lo[i][j]=l;
con[i*m+j].push_back(make_pair(i+1,j));
}
if(v>val[i+1][j]){
val[i+1][j]=v;
hi[i+1][j]=h;
lo[i+1][j]=l;
con[(i+1)*m+j].push_back(make_pair(i,j));
vector<bool>vi(n*m,false);
actualizar(con,i+1,j,vi);
}
}
if(j!=m-1){
int v=val[i][j+1]-hi[i][j+1]+lo[i][j+1]-1;
int h=max(A[i][j],hi[i][j+1]);
int l=min(A[i][j],lo[i][j+1]);
v+=h;
v-=l;
if(v>val[i][j]){
val[i][j]=v;
hi[i][j]=h;
lo[i][j]=l;
con[i*m+j].push_back(make_pair(i,j+1));
}
if(v>val[i][j+1]){
val[i][j+1]=v;
hi[i][j+1]=h;
lo[i][j+1]=l;
con[(i)*m+j+1].push_back(make_pair(i,j));
vector<bool>vi(n*m,false);
actualizar(con,i,j+1,vi);
}
h=max(A[i][j],A[i][j+1]);
l=min(A[i][j],A[i][j+1]);
v=h-l-2;
if(v>val[i][j]){
val[i][j]=v;
hi[i][j]=h;
lo[i][j]=l;
con[i*m+j].push_back(make_pair(i,j+1));
}
if(v>val[i][j+1]){
val[i][j+1]=v;
hi[i][j+1]=h;
lo[i][j+1]=l;
con[(i)*m+j+1].push_back(make_pair(i,j));
vector<bool>vi(n*m,false);
actualizar(con,i,j+1,vi);
}
}
ans=max(ans,val[i][j]);
}
}
cout<<ans;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
