Submission #13138

#	Time	Username	Problem	Language	Result	Execution time	Memory
13138		choyi0521	Split the sequence (APIO14_sequence)	C++98	0 / 100	1 ms	91708 KiB

sequence

#include<stdio.h>
#define MaxN 100001
typedef long long int lint;
typedef struct Line{
	lint m;
	lint b;
	int from;
	Line(){m=b=from=0;}
	Line(lint _m,lint _b,int _from){m=_m;b=_b;from=_from;}
}line;
line l[MaxN];
int ans[220][MaxN],p,sz;
int n,c;
lint sum[MaxN],dy1[MaxN],dy2[MaxN];
double cross(line i,line j){return (double)(i.b-j.b)/(j.m-i.m);}
void push(line t){
	while(sz>=2 && cross(t,l[sz])<cross(l[sz-1],l[sz])) sz--;
	l[++sz]=t;
}
int main(){
	int i,j;
	scanf("%d %d",&n,&c);
	for(i=1; i<=n; i++){
		scanf("%d",&sum[i]);
		sum[i]+=sum[i-1];
	}
	p=1;
	push(Line(0,0,0));
	for(i=1; i<=c; i++){
		for(j=i; j<n; j++){
			while(sz-p>=1 && cross(l[p],l[p+1])<=sum[j]&&l[p+1].from<j) p++;
			dy2[j]= l[p].m*sum[j]+l[p].b + sum[j]*(sum[n]-sum[j]);
			ans[i][j]=l[p].from;
		}
		p=1;
		sz=0;
		for(j=i; j<n; j++){
			dy1[j]=dy2[j];
			push(Line(sum[j],-sum[n]*sum[j]+dy1[j],j));
		}
	}
	lint max_=0;
	int pos,p[220],pcnt=0;
	for(i=1; i<=n; i++){
		if(max_<dy1[i]){
			max_=dy1[i];
			pos=i;
		}
	}
	while(pos!=0){
		p[++pcnt]=pos;
		pos=ans[c-pcnt+1][pos];
	}
	printf("%lld\n",max_);
	for(i=pcnt; i>=1; i--){
		printf("%d ",p[i]);
	}
	return 0;
}

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