Submission #15325

#	Time	Username	Problem	Language	Result	Execution time	Memory
15325		sujin	달리는 게임 (kriii3_E)	C++98	26 / 70	6 ms	16736 KiB

E

#include <cstdio>

#define N 1000001
#define M 1001

int n,a[M];
long long s[N],q,mx[M],t[M][M];


int main ()
{
	int i,j;
	long long as;

	scanf ("%d",&n);
	for (i=1;i<=n;i++)
		scanf ("%d",a+i),s[i]=s[i-1]+a[i];

	for (i=1;i<=n;i++)
		for (j=i;j<=n;j++)
			t[i][j]=t[i][j-1]+a[j]*(j-i+1);
	for (i=1;i<=n;i++)
		for (j=1;j<=n;j++)
			if (mx[i]<t[j][i])
				mx[i]=t[j][i];

	for (i=1;i<=n;i++)
	{
		if (mx[i]<mx[i-1])
			mx[i]=mx[i-1];
		for (j=1;j<=i;j++)
			if (mx[i] < mx[j-1]+t[j][i])
				mx[i] = mx[j-1]+t[j][i];
	
	}
	printf ("%lld\n",mx[n]);
	
}

• Subtask 1: 26 / 26
• Subtask 2: 0 / 44