oj.uz

Submission #359334

# Submission time Handle Problem Language Result Execution time Memory
359334 2021-01-26T20:39:00 Z ogibogi2004 Maxcomp (info1cup18_maxcomp) C++14
15 / 100
 12 ms 16768 KB 
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1024;
const int INF=2e9;
int a[MAXN][MAXN];
int opt1[MAXN][MAXN];
int opt2[MAXN][MAXN];
int opt3[MAXN][MAXN];
int opt4[MAXN][MAXN];
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>a[i][j];
		}
	}
	for(int i=0;i<MAXN;i++)
	{
		for(int j=0;j<MAXN;j++)
		{
			opt1[i][j]=-INF;
			opt2[i][j]=-INF;
			opt3[i][j]=-INF;
			opt4[i][j]=-INF;
		}
	}
	for(int i=n;i>0;i--)
	{
		for(int 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(int i=n;i>0;i--)
	{
		for(int 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(int i=1;i<=n;i++)
	{
		for(int 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(int i=1;i<=n;i++)
	{
		for(int 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);
		}
	}
	int ans=-INF;
	for(int i=1;i<=n;i++)
	{
		for(int 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 11 ms 16768 KB Output is correct
2 Correct 11 ms 16760 KB Output is correct
3 Correct 11 ms 16748 KB Output is correct
4 Correct 11 ms 16748 KB Output is correct
5 Correct 12 ms 16748 KB Output is correct
6 Correct 11 ms 16748 KB Output is correct
7 Correct 11 ms 16748 KB Output is correct
8 Incorrect 11 ms 16748 KB Output isn't correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 16748 KB Output is correct
2 Correct 11 ms 16748 KB Output is correct
3 Correct 12 ms 16748 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 16768 KB Output is correct
2 Correct 11 ms 16760 KB Output is correct
3 Correct 11 ms 16748 KB Output is correct
4 Correct 11 ms 16748 KB Output is correct
5 Correct 12 ms 16748 KB Output is correct
6 Correct 11 ms 16748 KB Output is correct
7 Correct 11 ms 16748 KB Output is correct
8 Incorrect 11 ms 16748 KB Output isn't correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 16768 KB Output is correct
2 Correct 11 ms 16760 KB Output is correct
3 Correct 11 ms 16748 KB Output is correct
4 Correct 11 ms 16748 KB Output is correct
5 Correct 12 ms 16748 KB Output is correct
6 Correct 11 ms 16748 KB Output is correct
7 Correct 11 ms 16748 KB Output is correct
8 Incorrect 11 ms 16748 KB Output isn't correct