Submission #6880

#	Time	Username	Problem	Language	Result	Execution time	Memory
6880		qja0950	Split the sequence (APIO14_sequence)	C++98	0 / 100	0 ms	131072 KiB

sequence

#include <stdio.h>

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

int N, K;
int A[MAXN];
int S[MAXN];

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

long long D[MAXK][MAXN][2];
int Stack[2][MAXN], Stackp;
bool MyOperator(int Linea[], int Lineb[]) {
	int Line[3][2];
	for(int i=0; i<3; i++) {
		Line[i][0]=Linea[i];
		Line[i][1]=Lineb[i];
	}
	ll temp1=(ll)(Line[1][1]-Line[0][1])*(ll)(Line[2][0]-Line[1][0]);
	ll temp2=(ll)(Line[2][1]-Line[1][1])*(ll)(Line[1][0]-Line[0][0]);
	return temp1>=temp2;
}
void Stack_Push(int k) {
	++Stackp;
	Stack[0][Stackp]=k;
	Stack[1][Stackp]=-k*k;
}
void Stack_Pop() {
	Stackp--;
}
void Trick() {
	int i;
	Stack_Push(S[1]);
	for(i=2; i<=N; i++) {
		if(A[i]==0) continue;
		else{
			Stack_Push(S[i]);
			i++;
			break;
		}
	}
	for(; i<=N; i++) {
		if(A[i]==0) continue;
		Stack_Push(S[i]);
		while(MyOperator(Stack[0]+Stackp-2, Stack[1]+Stackp-2)) {
			Stack_Pop();
			Stack_Pop();
			Stack_Push(S[i]);
		}
	}
}

long long MAX(long long x, long long y) {
	if(x>y) return x;
	else return y;
}
void Find(int i, int j);
void PROCESS() {
//	Trick();
	for(int i=1; i<=K; i++) {
		for(int j=i+1; j<=N; j++) {
			for(int k=i; k<j; k++) {
				int temp=D[i-1][k][0]-(S[k]*S[k])+S[j]*S[k];
				D[i][j][0]=MAX(D[i][j][0], temp);
				if(D[i][j][0]==temp) D[i][j][1]=k;
			}
		}
	}
	long long Ans=0;
	int p;
	for(int i=K+1; i<=N; i++) {
		Ans=MAX(Ans, D[K][i][0]);
		if(D[K][i][0]==Ans) p=i;
	}
	printf("%lld\n", Ans);
	Find(K, p);
}
void Find(int i, int j) {
	if(i==0) return;
	printf("%d ", D[i][j][1]);
	return Find(i-1, D[i][j][1]);
}
int main() {
	INPUT();
	PROCESS();
}

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