Submission #359335

#	Time	Username	Problem	Language	Result	Execution time	Memory
359335		ogibogi2004	Maxcomp (info1cup18_maxcomp)	C++14	15 / 100	21 ms	33132 KiB

maxcomp

#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
• Subtask 2: 15 / 15
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40