Submission #13457

#	Time	Username	Problem	Language	Result	Execution time	Memory
13457		ainta	Split the sequence (APIO14_sequence)	C++98	100 / 100	1823 ms	89064 KiB

sequence

#include<stdio.h>
int n, k, w[101000], top;
int Path[210][101000];
long long S[101000], D[2][101000];
struct Stack{
	long long a, b;
	int pv;
}st[101000];
void Add(long long a, long long b, int pv){
	while (top > 1 && (double)(st[top - 1].b - b) / (a - st[top - 1].a) <= (double)(st[top - 1].b - st[top].b) / (st[top].a - st[top - 1].a))top--;
	if (top && st[top].a == a){
		if (st[top].b < b)st[top].b = b;
		return;
	}
	top++;
	st[top].a = a, st[top].b = b, st[top].pv = pv;
}
long long Gap(int t, long long x){
	return st[t].a*x + st[t].b;
}
long long Do(long long x){
	int be = 1, ed = top - 1, mid, r = top;
	while (be <= ed){
		mid = (be + ed) >> 1;
		if (Gap(mid, x) >= Gap(mid + 1, x)){
			r = mid;
			ed = mid - 1;
		}
		else{
			be = mid + 1;
		}
	}
	return r;
}
int Ans[210];
int main(){
	int i, j, t, pv = 0;
	scanf("%d%d", &n, &k);
	k++;
	for (i = 1; i <= n; i++){
		scanf("%d", &w[i]);
		S[i] = S[i - 1] + w[i];
	}
	for (i = 2; i <= k; i++){
		top = 0;
		pv = !pv;
		for (j = i; j <= n; j++){
			Add(S[j - 1], D[!pv][j - 1] - S[j - 1] * S[j - 1], j - 1);
			t = Do(S[j]);
			D[pv][j] = Gap(t, S[j]);
			Path[i][j] = st[t].pv;
		}
	}
	printf("%lld\n", D[pv][n]);
	t = n;
	for (i = k; i >= 2; i--){
		t = Path[i][t];
		Ans[i] = t;
	}
	for (i = 2; i <= k; i++)printf("%d ", Ans[i]);
}

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