Submission #7986

#	Time	Username	Problem	Language	Result	Execution time	Memory
7986		gs13068	Split the sequence (APIO14_sequence)	C++98	100 / 100	1704 ms	81948 KiB

sequence

#include<cstdio>

long long a[100001];
long long d[2][100001];
long long *now, *next;
int v[201][100001];

void dfs(int p,int s,int e,int f,int r)
{
	if(s<=e)
	{
		int i,t=(s+e)/2;
		next[t]=9e18;
		for(i=f;i<=t&&i<=r;i++)if(next[t]>now[i]+(a[t]-a[i])*(a[t]-a[i]))
		{
			next[t]=now[i]+(a[t]-a[i])*(a[t]-a[i]);
			v[p][t]=i;
		}
		dfs(p,s,t-1,f,v[p][t]);
		dfs(p,t+1,e,v[p][t],r);
	}
}

void print(int i,int j)
{
    if(i)
    {
        print(i-1,v[i][j]);
        printf("%d ",v[i][j]);
    }
}

int main()
{
	long long *temp;
	int i,n,m;
	scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
		a[i]+=a[i-1];
	}
	now=d[0];
	next=d[1];
	for(i=1;i<=n;i++)now[i]=a[i]*a[i];
    for(i=1;i<=m;i++)
	{
        dfs(i,i,n,i,n);
        temp=now;
        now=next;
        next=temp;
	}
	printf("%lld\n",(a[n]*a[n]-now[n])/2);
	print(m,n);
}

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