Submission #8110

#	Time	Username	Problem	Language	Result	Execution time	Memory
8110		qja0950	Split the sequence (APIO14_sequence)	C++98	100 / 100	1628 ms	91524 KiB

sequence

#include <stdio.h>

#define MAXK 222
#define MAXN 101101
typedef long long ll;

int N, K;
int Number[MAXN];
ll Sum[MAXN];

void INPUT() {
	scanf("%d %d", &N, &K);
	for(int i=1; i<=N; i++) {
		scanf("%d", &Number[i]);
		Sum[i] = Sum[i-1] + (ll)Number[i];
	}
}

int Mom[MAXK][MAXN];
ll Dy[2][MAXN];
void Get(int k, int a, int b, int ga, int gb) {
	if(a>b) return;
	int now  = k%2;
	int past = 1 - now;
	int m = (a + b)/2;
	ll max = -1;
	int maxp = 0;
	for(int i=ga; i<=gb; i++) {
		if(i>=m) break;
		ll current = Dy[past][i] + Sum[i]*(Sum[m] - Sum[i]);
		if(max<current) {
			max  = current;
			maxp = i ;
		}
	}
	 Dy[now][m] = max;
	Mom[k  ][m] = maxp;
	Get(k, a, m-1, ga, maxp);
	Get(k, m+1, b, maxp, gb);
}
void Find(int k, int n) {
	if(k==1) return;
	Find(k-1, Mom[k][n]);
	printf("%d ", Mom[k][n]);
}
int main() {
	INPUT();
	for(int i=2; i<=K+1; i++)
		Get( i, i, N, i-1, N-1 );
	printf("%lld\n", Dy[1-K%2][N]);
	Find(K+1, N);
}

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