Submission #5686

#	Time	Username	Problem	Language	Result	Execution time	Memory
5686		cki86201	Split the sequence (APIO14_sequence)	C++98	100 / 100	516 ms	85860 KiB

sequence

#include<stdio.h>
#include<set>

typedef long long ll;
typedef std::pair<ll,ll> pl;
#define X first
#define Y second

int n, k, s[100010];
ll d[2][100010];
int b[202][100010];
int ans[202];
struct deq{
	pl p[100010];
	int w[100010];
	int f, r;
	void init(){f=r=0;}
	void push(pl x,int c){
		while(f-r>1 && (p[f-1].X - p[f-2].X) * (x.Y - p[f-1].Y) >= (x.X - p[f-1].X) * (p[f-1].Y - p[f-2].Y))--f;
		p[f] = x, w[f++] = c;
	}
	ll pop(ll x){
		while(f-r>1 && (x*p[r].X + p[r].Y) <= (x*p[r+1].X + p[r+1].Y))++r;
		return x*p[r].X + p[r].Y;
	}
	inline int prev(){return w[r];}
}Deq[2];

int main()
{
	scanf("%d%d",&n,&k);
	int i;
	for(i=1;i<=n;i++)scanf("%d",s+i);
	for(i=1;i<=n;i++)s[i] += s[i-1];
	for(int j=1;j<=k;j++){
		int t = j&1;
		Deq[t].init();
		for(i=1;i<=n;i++){
			d[t][i] = Deq[!t].pop(s[i]);
			b[j][i] = Deq[!t].prev();
			Deq[!t].push(pl(s[i], d[!t][i] - (ll)s[i]*s[i]), i);
		}
	}
	printf("%lld\n",d[k&1][n]);
	int now = n;
	for(i=k;i;i--)now = b[i][now], ans[i] = now;
	for(i=1;i<=k;i++)printf("%d ",ans[i]);
	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