oj.uz

답안 #6972

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
6972 2014-07-12T01:11:51 Z Qwaz 수열 (APIO14_sequence) C++
0 / 100
 0 ms 131072 KB 
#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.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Memory limit exceeded 0 ms 131072 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Halted 0 ms 0 KB -

Subtask #3
0.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Halted 0 ms 0 KB -

Subtask #4
0.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Halted 0 ms 0 KB -

Subtask #5
0.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Halted 0 ms 0 KB -

Subtask #6
0.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Halted 0 ms 0 KB -