Submission #6972

#	Time	Username	Problem	Language	Result	Execution time	Memory
6972		Qwaz	수열 (APIO14_sequence)	C++98	0 / 100	0 ms	131072 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;

	CHT() : top(0), now(0) {}

	void insert(ll nowCo, ll nowCon, int nowNum){
		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][CUT];
int trace[MAX][CUT];
CHT convexHull[CUT];

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<=i; j++){
			convexHull[j-1].insert(2*sum[i-1], dp[i-1][j-1]-sum[i-1]*(sum[n]+sum[i-1]), i-1);

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

	printf("%lld\n", dp[n][numCut+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: 0 / 11
• Subtask 2: 0 / 11
• Subtask 3: 0 / 11
• Subtask 4: 0 / 17
• Subtask 5: 0 / 21
• Subtask 6: 0 / 29