oj.uz

Submission #6881

# Submission time Handle Problem Language Result Execution time Memory
6881 2014-07-09T05:26:12 Z qja0950 Split the sequence (APIO14_sequence) C++
50 / 100
 2000 ms 91920 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 91920 KB Output is correct - contestant found the optimal answer: 108 == 108
2 Correct 0 ms 91920 KB Output is correct - contestant found the optimal answer: 999 == 999
3 Correct 0 ms 91920 KB Output is correct - contestant found the optimal answer: 0 == 0
4 Correct 0 ms 91920 KB Output is correct - contestant found the optimal answer: 1542524 == 1542524
5 Correct 0 ms 91920 KB Output is correct - contestant found the optimal answer: 4500000000 == 4500000000
6 Correct 0 ms 91920 KB Output is correct - contestant found the optimal answer: 1 == 1
7 Correct 0 ms 91920 KB Output is correct - contestant found the optimal answer: 1 == 1
8 Correct 0 ms 91920 KB Output is correct - contestant found the optimal answer: 1 == 1
9 Correct 0 ms 91920 KB Output is correct - contestant found the optimal answer: 100400096 == 100400096
10 Correct 0 ms 91920 KB Output is correct - contestant found the optimal answer: 900320000 == 900320000
11 Correct 0 ms 91920 KB Output is correct - contestant found the optimal answer: 3698080248 == 3698080248
12 Correct 0 ms 91920 KB Output is correct - contestant found the optimal answer: 3200320000 == 3200320000
13 Correct 0 ms 91920 KB Output is correct - contestant found the optimal answer: 140072 == 140072
14 Correct 0 ms 91920 KB Output is correct - contestant found the optimal answer: 376041456 == 376041456
15 Correct 0 ms 91920 KB Output is correct - contestant found the optimal answer: 805 == 805
16 Correct 0 ms 91920 KB Output is correct - contestant found the optimal answer: 900189994 == 900189994
17 Correct 0 ms 91920 KB Output is correct - contestant found the optimal answer: 999919994 == 999919994

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 91920 KB Output is correct - contestant found the optimal answer: 1093956 == 1093956
2 Correct 0 ms 91920 KB Output is correct - contestant found the optimal answer: 302460000 == 302460000
3 Correct 0 ms 91920 KB Output is correct - contestant found the optimal answer: 122453454361 == 122453454361
4 Correct 0 ms 91920 KB Output is correct - contestant found the optimal answer: 93663683509 == 93663683509
5 Correct 0 ms 91920 KB Output is correct - contestant found the optimal answer: 1005304678 == 1005304678
6 Correct 0 ms 91920 KB Output is correct - contestant found the optimal answer: 933702 == 933702
7 Correct 0 ms 91920 KB Output is correct - contestant found the optimal answer: 25082842857 == 25082842857
8 Correct 0 ms 91920 KB Output is correct - contestant found the optimal answer: 687136 == 687136
9 Correct 0 ms 91920 KB Output is correct - contestant found the optimal answer: 27295930079 == 27295930079
10 Correct 0 ms 91920 KB Output is correct - contestant found the optimal answer: 29000419931 == 29000419931

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 91920 KB Output is correct - contestant found the optimal answer: 610590000 == 610590000
2 Correct 0 ms 91920 KB Output is correct - contestant found the optimal answer: 311760000 == 311760000
3 Correct 4 ms 91920 KB Output is correct - contestant found the optimal answer: 1989216017013 == 1989216017013
4 Correct 0 ms 91920 KB Output is correct - contestant found the optimal answer: 1499437552673 == 1499437552673
5 Correct 4 ms 91920 KB Output is correct - contestant found the optimal answer: 1019625819 == 1019625819
6 Correct 4 ms 91920 KB Output is correct - contestant found the optimal answer: 107630884 == 107630884
7 Correct 4 ms 91920 KB Output is correct - contestant found the optimal answer: 475357671774 == 475357671774
8 Correct 0 ms 91920 KB Output is correct - contestant found the optimal answer: 193556962 == 193556962
9 Correct 0 ms 91920 KB Output is correct - contestant found the optimal answer: 482389919803 == 482389919803
10 Correct 0 ms 91920 KB Output is correct - contestant found the optimal answer: 490686959791 == 490686959791

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 91920 KB Output is correct - contestant found the optimal answer: 21503404 == 21503404
2 Correct 0 ms 91920 KB Output is correct - contestant found the optimal answer: 140412195 == 140412195
3 Correct 164 ms 91920 KB Output is correct - contestant found the optimal answer: 49729674225461 == 49729674225461
4 Correct 0 ms 91920 KB Output is correct - contestant found the optimal answer: 37485571387523 == 37485571387523
5 Correct 160 ms 91920 KB Output is correct - contestant found the optimal answer: 679388326 == 679388326
6 Correct 140 ms 91920 KB Output is correct - contestant found the optimal answer: 4699030287 == 4699030287
7 Correct 164 ms 91920 KB Output is correct - contestant found the optimal answer: 12418819758185 == 12418819758185
8 Correct 160 ms 91920 KB Output is correct - contestant found the optimal answer: 31093317350 == 31093317350
9 Correct 36 ms 91920 KB Output is correct - contestant found the optimal answer: 12194625429236 == 12194625429236
10 Correct 72 ms 91920 KB Output is correct - contestant found the optimal answer: 12345131038664 == 12345131038664

Subtask #5
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 280 ms 91920 KB Output is correct - contestant found the optimal answer: 1818678304 == 1818678304
2 Correct 256 ms 91920 KB Output is correct - contestant found the optimal answer: 1326260195 == 1326260195
3 Execution timed out 2000 ms 91916 KB Program timed out
4 Halted 0 ms 0 KB -

Subtask #6
0.0 / 29.0

# Verdict Execution time Memory Grader output
1 Halted 0 ms 0 KB -