#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <utility>
#include <queue>
#include <map>
#include <array>
#include <iomanip>
#include <fstream>
#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;
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
int n,m;
cin>>n>>m;
vector<vector<int> >A(n);
vector<int>a(m,-1);
vector<int>b(m);
vector<vector<int> >val(n);
vector<vector<int> >lo(n);
vector<vector<int> >hi(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];
}
}
int ans=-1;
for(int j=0;j<m;j++){
for(int i=0;i<n;i++){
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;
val[i-1][j]=v;
hi[i-1][j]=h;
lo[i-1][j]=l;
}
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;
val[i-1][j]=v;
hi[i-1][j]=h;
lo[i-1][j]=l;
}
}
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;
val[i][j-1]=v;
hi[i][j-1]=h;
lo[i][j-1]=l;
}
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;
val[i][j-1]=v;
hi[i][j-1]=h;
lo[i][j-1]=l;
}
}
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;
val[i+1][j]=v;
hi[i+1][j]=h;
lo[i+1][j]=l;
}
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;
val[i+1][j]=v;
hi[i+1][j]=h;
lo[i+1][j]=l;
}
}
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;
val[i][j+1]=v;
hi[i][j+1]=h;
lo[i][j+1]=l;
}
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;
val[i][j+1]=v;
hi[i][j+1]=h;
lo[i][j+1]=l;
}
}
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 |
- |
