#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAXN=1024;
const ll INF=2e15;
ll a[MAXN][MAXN];
ll opt1[MAXN][MAXN];
ll opt2[MAXN][MAXN];
ll opt3[MAXN][MAXN];
ll opt4[MAXN][MAXN];
int main()
{
ll n,m;
cin>>n>>m;
for(ll i=1;i<=n;i++)
{
for(ll j=1;j<=m;j++)
{
cin>>a[i][j];
}
}
for(ll i=0;i<MAXN;i++)
{
for(ll j=0;j<MAXN;j++)
{
opt1[i][j]=-INF;
opt2[i][j]=-INF;
opt3[i][j]=-INF;
opt4[i][j]=-INF;
}
}
for(ll i=n;i>0;i--)
{
for(ll j=m;j>0;j--)
{
opt1[i][j]=max(opt1[i][j+1],opt1[i+1][j]);
opt1[i][j]=max(opt1[i][j],-a[i][j]-i-j);
}
}
for(ll i=n;i>0;i--)
{
for(ll j=1;j<=m;j++)
{
opt2[i][j]=max(opt2[i][j-1],opt2[i+1][j]);
opt2[i][j]=max(opt2[i][j],-a[i][j]-i+j);
}
}
for(ll i=1;i<=n;i++)
{
for(ll j=m;j>0;j--)
{
opt3[i][j]=max(opt3[i][j+1],opt3[i-1][j]);
opt3[i][j]=max(opt3[i][j],-a[i][j]+i-j);
}
}
for(ll i=1;i<=n;i++)
{
for(ll j=1;j<=m;j++)
{
opt4[i][j]=max(opt4[i][j-1],opt4[i-1][j]);
opt4[i][j]=max(opt4[i][j],-a[i][j]+i+j);
}
}
ll ans=-INF;
for(ll i=1;i<=n;i++)
{
for(ll j=1;j<=m;j++)
{
/*cout<<i<<" "<<j<<":\n";
cout<<opt1[i][j]<<" "<<opt2[i][j]<<" "<<opt3[i][j]<<" "<<opt4[i][j]<<endl;
cout<<a[i][j]+i+j+opt1[i][j]<<endl;
cout<<a[i][j]+i-j+opt2[i][j]<<endl;
cout<<a[i][j]-i+j+opt3[i][j]<<endl;
cout<<a[i][j]-i-j+opt4[i][j]<<endl;*/
ans=max(ans,a[i][j]+i+j+opt1[i][j]);
ans=max(ans,a[i][j]+i-j+opt2[i][j]);
ans=max(ans,a[i][j]-i+j+opt3[i][j]);
ans=max(ans,a[i][j]-i-j+opt4[i][j]);
}
}
cout<<ans-1<<endl;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
33132 KB |
Output is correct |
2 |
Correct |
20 ms |
33132 KB |
Output is correct |
3 |
Correct |
20 ms |
33132 KB |
Output is correct |
4 |
Correct |
20 ms |
33132 KB |
Output is correct |
5 |
Correct |
21 ms |
33132 KB |
Output is correct |
6 |
Correct |
20 ms |
33260 KB |
Output is correct |
7 |
Correct |
20 ms |
33132 KB |
Output is correct |
8 |
Correct |
20 ms |
33132 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
33132 KB |
Output is correct |
2 |
Correct |
20 ms |
33132 KB |
Output is correct |
3 |
Correct |
20 ms |
33132 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
33132 KB |
Output is correct |
2 |
Correct |
20 ms |
33132 KB |
Output is correct |
3 |
Correct |
20 ms |
33132 KB |
Output is correct |
4 |
Correct |
20 ms |
33132 KB |
Output is correct |
5 |
Correct |
21 ms |
33132 KB |
Output is correct |
6 |
Correct |
20 ms |
33260 KB |
Output is correct |
7 |
Correct |
20 ms |
33132 KB |
Output is correct |
8 |
Correct |
20 ms |
33132 KB |
Output is correct |
9 |
Correct |
21 ms |
33388 KB |
Output is correct |
10 |
Correct |
21 ms |
33388 KB |
Output is correct |
11 |
Correct |
21 ms |
33388 KB |
Output is correct |
12 |
Correct |
21 ms |
33388 KB |
Output is correct |
13 |
Correct |
23 ms |
33388 KB |
Output is correct |
14 |
Correct |
21 ms |
33388 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
33132 KB |
Output is correct |
2 |
Correct |
20 ms |
33132 KB |
Output is correct |
3 |
Correct |
20 ms |
33132 KB |
Output is correct |
4 |
Correct |
20 ms |
33132 KB |
Output is correct |
5 |
Correct |
21 ms |
33132 KB |
Output is correct |
6 |
Correct |
20 ms |
33260 KB |
Output is correct |
7 |
Correct |
20 ms |
33132 KB |
Output is correct |
8 |
Correct |
20 ms |
33132 KB |
Output is correct |
9 |
Correct |
20 ms |
33132 KB |
Output is correct |
10 |
Correct |
20 ms |
33132 KB |
Output is correct |
11 |
Correct |
20 ms |
33132 KB |
Output is correct |
12 |
Correct |
21 ms |
33388 KB |
Output is correct |
13 |
Correct |
21 ms |
33388 KB |
Output is correct |
14 |
Correct |
21 ms |
33388 KB |
Output is correct |
15 |
Correct |
21 ms |
33388 KB |
Output is correct |
16 |
Correct |
23 ms |
33388 KB |
Output is correct |
17 |
Correct |
21 ms |
33388 KB |
Output is correct |
18 |
Correct |
416 ms |
49220 KB |
Output is correct |
19 |
Correct |
414 ms |
49772 KB |
Output is correct |
20 |
Correct |
397 ms |
49388 KB |
Output is correct |
21 |
Correct |
420 ms |
49644 KB |
Output is correct |
22 |
Correct |
415 ms |
49752 KB |
Output is correct |
23 |
Correct |
417 ms |
49816 KB |
Output is correct |
24 |
Correct |
431 ms |
50028 KB |
Output is correct |