Submission #6881

#	Time	Username	Problem	Language	Result	Execution time	Memory
6881		qja0950	Split the sequence (APIO14_sequence)	C++98	50 / 100	2000 ms	91920 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[2][MAXN];
int Mom[MAXK][MAXN];
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]);
		}
	}
}

ll MAX(ll x, ll 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++) D[i%2][j]=0;
		for(int j=i+1; j<=N; j++) {
			for(int k=i; k<j; k++) {
				ll temp=D[1-i%2][k]-((ll)S[k]*(ll)S[k])+(ll)S[j]*(ll)S[k];
				D[i%2][j]=MAX(D[i%2][j], temp);
				if(D[i%2][j]==temp) Mom[i][j]=k;
			}
		}
	}
	long long Ans=0;
	int p=N;
	Ans=MAX(Ans, D[K%2][N]);
	printf("%lld\n", Ans);
	Find(K, p);
}
void Find(int i, int j) {
	if(i==0) return;
	printf("%d ", Mom[i][j]);
	return Find(i-1, Mom[i][j]);
}
int main() {
	INPUT();
	PROCESS();
}

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