Submission #5794

#	Time	Username	Problem	Language	Result	Execution time	Memory
5794		gs12037	Split the sequence (APIO14_sequence)	C++98	33 / 100	0 ms	81564 KiB

sequence

#include <stdio.h>
#include <algorithm>
#define M 100009
using namespace std;

int n, k,path[200][M];
long long int d[2][M],ans,s[M];

long long int f(int j, int r){
	return d[0][r] + (s[n] - s[j])*(s[j] - s[r]);
}
int main(){
	int i, j;
	scanf("%d %d", &n, &k);
	for (i = 1; i <= n; i++) scanf("%lld", &s[i]);
	for (i = 1; i <= n; i++) s[i] = s[i - 1] + s[i];

	int pivot;
	for (i = 1; i <= k; i++){
		pivot = i - 1;
		for (j = 1; j <= n; j++){
			while (f(j, pivot) <= f(j, pivot + 1) && pivot < j-1) pivot++;
			d[1][j] = f(j, pivot);
			path[i][j] = pivot;
		}
		for (j = 1; j <= n; j++) d[0][j] = d[1][j];
	}

	for (j = 1; j <= n; j++) ans = max(ans, d[1][j]);
	printf("%lld\n", ans);

	for (j = 1; j <= n; j++){
		if (ans == d[1][j]){
			int temp = j;
			for (i = k; i >= 1; i--){
				s[i] = temp;
				temp = path[i][temp];
			}
			break;
		}
	}
	for (i = 1; i <= k; i++) printf("%lld ", s[i]);
	return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 0 / 17
• Subtask 5: 0 / 21
• Subtask 6: 0 / 29