oj.uz

Submission #6973

# Submission time Handle Problem Language Result Execution time Memory
6973 2014-07-12T01:20:41 Z Qwaz Split the sequence (APIO14_sequence) C++
0 / 100
 0 ms 93684 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;

	void init(){
		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][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
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 93684 KB Output is correct - contestant found the optimal answer: 108 == 108
2 Incorrect 0 ms 93684 KB Output isn't correct - contestant didn't find the optimal answer: 774 < 999
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Halted 0 ms 0 KB -

Subtask #3
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Halted 0 ms 0 KB -

Subtask #4
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Halted 0 ms 0 KB -

Subtask #5
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Halted 0 ms 0 KB -

Subtask #6
0.0 / 29.0

# Verdict Execution time Memory Grader output
1 Halted 0 ms 0 KB -