Submission #1313441

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313441		neonglitch	Mean (info1cup19_mean)	C++20	100 / 100	5 ms	568 KiB

mean

#include <iostream>
using namespace std;
const int N=202;
int dp[N][N],a[N];
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin>>n;
	for(int i=0;i<=n+1;i++){
		for(int j=0;j<=n+1;j++)
		{
			dp[i][j]=-1e9;
		}
	}
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		dp[i][i]=a[i];
	}
	for(int len=2;len<=n;len++)
	{
		for(int l=1;l+len-1<=n;l++)
		{
			int r=l+len-1;
			for(int p=l;p<r;p++)
			{
				dp[l][r]=max(dp[l][r],(dp[l][p]+dp[p+1][r])/2);
			}
			dp[l][r]=max(dp[l][r],(dp[l+2][r]+((a[l]+a[l+1])/2))/2);
			dp[l][r]=max(dp[l][r],(dp[l][r-2]+((a[r]+a[r-1])/2))/2);
			for(int p=l+1;p+1<r;p++)
			{
				int a0=dp[l][p-1];
				int a1=(a[p]+a[p+1])/2;
				int a2=dp[p+2][r];
				
				int a01=(a0+a1)/2;
				int a12=(a1+a2)/2;
				dp[l][r]=max(dp[l][r],(a01+a2)/2);
				dp[l][r]=max(dp[l][r],(a12+a0)/2);
			}
		}
	}
	cout<<dp[1][n]<<endl;
}

• Subtask 1: 30 / 30
• Subtask 2: 70 / 70