Submission #7611

#	Time	Username	Problem	Language	Result	Execution time	Memory
7611		hongjun7	Split the sequence (APIO14_sequence)	C++98	100 / 100	568 ms	84024 KiB

sequence

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define MK 202
#define MN 100002
int N, K, i, j, k, X[MN], _k = 1, best[MK][MN], s[MN], b;
long long d[2][MN], f[MN], S[MN];
bool ok(int z) {
	int x = s[b-1], y = s[b];
	return (f[y]-f[x])*(S[y]-S[z]) >= (f[z]-f[y]) *(S[x]-S[y]);
}
int main() {
	int x;
	scanf("%d%d",&N,&K);
	for (i = 1; i <= N; i++) {
		scanf("%d", &X[i]);
		S[i] = S[i-1] + X[i];
	}
	for (i = 0; i <= N; i++) d[0][i] = -1;
	for (k = 2; k <= K+1; k++) {
		_k = k&1;
		for (i = 0; i <= N; i++) d[_k][i] = 0;
		b = -1; x = 1;
		s[++b] = 0; s[++b] = 1;
		for (i = 0; i <= N; i++) f[i] = d[!(_k)][i]-S[i]*S[i];
		for (i = 2; i <= N; i++) {
			if (x > b) x = b;
			while (x < b && (f[s[x]]-f[s[x+1]]) <= (S[s[x+1]] - S[s[x]])*S[i]) x++;
			d[_k][i] = f[s[x]]+S[s[x]]*S[i];
			best[k][i] = s[x];
			while (b >= x && ok(i)) b--;
			s[++b] = i;
		}
	}
	printf("%lld\n",d[_k][N]);
	x = N;
	vector <int> res;
	for (i = K+1; i > 1; i--) {
		x = best[i][x];
		res.push_back(x);
	}
	reverse(res.begin(), res.end());
	for (i = 0; i < res.size(); i++) printf("%d ",res[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