제출 #7864

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
7864		gs13068	수열 (APIO14_sequence)	C++98	100 / 100	696 ms	84292 KiB

sequence

#include<cstdio>
#include<algorithm>

std::pair<std::pair<long long,long long>,int> s[100000];
int sn;

long long a[100001];
long long d[2][100001];
int vi[201][100001];

void insert(long long a,long long b,int c)
{
	double t;
    while(sn>=2)
	{
		t = -1.*(s[sn-1].first.second-s[sn-2].first.second)/(s[sn-1].first.first-s[sn-2].first.first);
        if(t*a+b>t*s[sn-1].first.first+s[sn-1].first.second)break;
        sn--;
	}
	s[sn++]=std::make_pair(std::make_pair(a,b),c);
}

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

int main()
{
	int i,j,k,n,m;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
		a[i]+=a[i-1];
		d[0][i]=a[i]*a[i];
	}
	for(i=1;i<=m;i++)
	{
		k=0;
		sn=0;
		for(j=1;j<=n;j++)
		{
			insert(-2*a[j-1],a[j-1]*a[j-1]+d[!(i&1)][j-1],j-1);
			if(k>=sn)k=sn-1;
			while(k+1<sn)
			{
                if(-(s[k+1].first.second-s[k].first.second)<a[j]*(s[k+1].first.first-s[k].first.first))break;
				k++;
			}
			d[i&1][j]=a[j]*a[j]+s[k].first.first*a[j]+s[k].first.second;
			vi[i][j]=s[k].second;
		}
	}
	printf("%lld\n",(a[n]*a[n]-d[m&1][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