Submission #6873

#	Time	Username	Problem	Language	Result	Execution time	Memory
6873		woqja125	Split the sequence (APIO14_sequence)	C++98	50 / 100	2000 ms	85464 KiB

sequence

#include<stdio.h>
int dat[100001], s[100001];
long long dp[2][100001];
int p[210][100001];
int main()
{
	int n, k;
	int i, j, l;
	scanf("%d%d", &n, &k); k++;
	for(i=1; i<=n; i++)
	{
		scanf("%d", &dat[i]);
		s[i] = s[i-1] + dat[i];
	}
	for(i=0; i<=1; i++)for(j=0; j<=n; j++) dp[i][j]=-1;
	dp[0][0] = 0;
	for(i=1; i<=k; i++)
	{
		for(j=0; j<=n; j++) dp[i%2][j]=-1;
		for(j=1; j<=n; j++)
		{
			long long max = -1;
			int x = -1;
			long long *D = dp[(i-1)%2];
			for(l=0; l<j; l++)
			{
				if(D[l] == -1) continue;
				long long t = D[l] - 1ll*s[l]*s[l] + 1ll*s[l]*s[j];
				if(max < t)
				{	
					max = t;
					x = l;
				}
			}
			p[i][j] = x;
			dp[i%2][j] = max;
		}
	}
	printf("%lld\n", dp[k%2][n]);
	int x = n;
	for(int i=k; i>1; i--)
	{
		x = p[i][x];
		printf("%d ", x);
	}
	return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 17 / 17
• Subtask 5: 0 / 21
• Subtask 6: 0 / 29