Submission #6997

#	Time	Username	Problem	Language	Result	Execution time	Memory
6997		Qwaz	Split the sequence (APIO14_sequence)	C++98	100 / 100	560 ms	93684 KiB

sequence

#include <cstdio>
#include <algorithm>

using namespace std;
typedef long long ll;
typedef pair < ll, int > pli;
const int MAX = 100020, CUT = 220;

struct CHT {
	int num[MAX];
	ll co[MAX], con[MAX];
	int top, now;

	void init(){
		top = 0;
		now = 0;
	}

	void insert(ll nowCo, ll nowCon, int nowNum){
		if(top >= 1 && nowCo == co[top-1]){
			num[top-1] = nowNum;
			return;
		}

		while(top >= 2 && (con[top-1]-con[top-2])*(co[top-2]-nowCo) >= (nowCon-con[top-2])*(co[top-2]-co[top-1]))
			top--;

		co[top] = nowCo;
		con[top] = nowCon;
		num[top] = nowNum;
		top++;

		if(now >= top) now = top-1;
	}

	pli getMax(ll x){
		while(now < top-1 && co[now+1]*x + con[now+1] > co[now]*x + con[now])
			now++;

		return pli(co[now]*x + con[now], num[now]);
	}
};

int n, numCut, data[MAX];
ll sum[MAX];

void input(){
	scanf("%d%d", &n, &numCut);

	int i;
	for(i = 1; i<=n; i++){
		scanf("%d", &data[i]);
		sum[i] = sum[i-1]+data[i];
	}
}

ll dp[MAX][2];
int trace[MAX][CUT];
CHT convexHull[2];

void solve(){
	int i, j;
	for(i = 1; i<=n; i++)
		dp[i][1] = sum[i]*(sum[n]-sum[i]);
	for(j = 2; j<=numCut+1; j++){
		bool c = j&1;
		convexHull[!c].init();
		for(i = j; i<=n; i++){
			convexHull[!c].insert(2*sum[i-1], dp[i-1][!c]-sum[i-1]*(sum[n]+sum[i-1]), i-1);

			pli t = convexHull[!c].getMax(sum[i]);
			dp[i][c] = t.first+sum[i]*(sum[n]-sum[i]);
			trace[i][j] = t.second;
		}
	}

	printf("%lld\n", dp[n][(numCut+1)&1]>>1);
}

void traceRoute(){
	int p = n, q = numCut+1;

	while(q > 1){
		printf("%d ", trace[p][q]);
		p = trace[p][q];
		q--;
	}

	puts("");
}

int main(){
	input();

	solve();
	traceRoute();

	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