oj.uz

Submission #359335

# Submission time Handle Problem Language Result Execution time Memory
359335 2021-01-26T20:40:11 Z ogibogi2004 Maxcomp (info1cup18_maxcomp) C++14
15 / 100
 21 ms 33132 KB 
#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(opt1[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;
}

Subtask #1
0 / 15.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 20 ms 33132 KB Output is correct
6 Correct 20 ms 33132 KB Output is correct
7 Correct 20 ms 33132 KB Output is correct
8 Incorrect 20 ms 33132 KB Output isn't correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 33132 KB Output is correct
2 Correct 20 ms 33132 KB Output is correct
3 Correct 20 ms 33132 KB Output is correct

Subtask #3
0 / 30.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 20 ms 33132 KB Output is correct
6 Correct 20 ms 33132 KB Output is correct
7 Correct 20 ms 33132 KB Output is correct
8 Incorrect 20 ms 33132 KB Output isn't correct

Subtask #4
0 / 40.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 20 ms 33132 KB Output is correct
6 Correct 20 ms 33132 KB Output is correct
7 Correct 20 ms 33132 KB Output is correct
8 Incorrect 20 ms 33132 KB Output isn't correct