Submission #6982

#	Time	Username	Problem	Language	Result	Execution time	Memory
6982		woqja125	Split the sequence (APIO14_sequence)	C++98	100 / 100	576 ms	86636 KiB

sequence

#include<stdio.h>
int dat[100001], s[100001];
long long dp[2][100001];
long long Y[100001];
int p[210][100001];
int stk[100001], b;
inline bool cmp(long long *D, int z)
{
	int x, y;
	x = stk[b-1];
	y = stk[b];

	return (Y[y]-Y[x])*(s[y]-s[z]) >= (Y[z]-Y[y]) *(s[x]-s[y]);
}
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;
	for(j=0; j<=n; j++)
	{
		dp[1][j] = 0;
	}
	for(i=2; i<=k; i++)
	{
		for(j=0; j<=n; j++) dp[i%2][j]=0;
		long long *D = dp[(i-1)%2];
		b = -1;
		int x=1;
		stk[++b] = 0; stk[++b] = 1;
		for(j=0; j<=n; j++) Y[j] = D[j] - 1ll*s[j]*s[j];
		for(l=2; l<=n; l++)
		{
			if(x>b) x = b;
			while(x < b && (Y[stk[x]] - Y[stk[x+1]]) <= 1ll*(s[stk[x+1]] - s[stk[x]])*s[l] ) x++;
			dp[i%2][l] = D[stk[x]] - 1ll*s[stk[x]]*s[stk[x]] + 1ll*s[stk[x]]*s[l];
			p[i][l] = stk[x];
			while( b>=x && cmp(D, l) ) b--;
			stk[++b] = l;
		}
	}
	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: 21 / 21
• Subtask 6: 29 / 29