Submission #61496

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
61496	2018-07-26T05:47:36 Z	ainta(#1774)	Homecoming (BOI18_homecoming)	C++11	0 / 100	93 ms	16360 KB

homecoming

#include "homecoming.h"
#include <algorithm>
#define N_ 2010000
using namespace std;

int A[N_], B[N_], n, K;
long long D[N_][2], res;

void Do() {
	int i;
	for (i = 0; i <= n; i++)D[i][0] = D[i][1] = -1e18;
	D[1][0] = B[1];
	for (i = 2; i <= n; i++) {
		D[i][0] = D[i - 1][0] + B[i];
		if (i > K)D[i][0] = max(D[i][0], D[i - K][1]);
		D[i][1] = max(max(D[i - 1][1], D[i - 1][0]) + A[i], D[i][0]);
	}
	res = max(res, D[n][0]);
	for (i = 0; i <= n; i++)D[i][0] = D[i][1] = -1e18;
	D[1][1] = A[1];
	for (i = 2; i <= n; i++) {
		D[i][0] = D[i - 1][0] + B[i];
		if (i > K)D[i][0] = max(D[i][0], D[i - K][1]);
		D[i][1] = max(max(D[i - 1][1], D[i - 1][0]) + A[i], D[i][0]);
	}
	res = max(res, max(D[n][0], D[n][1]));
}

void Rotate() {
	int i;
	int ta = A[1], tb = B[1];
	for (i = 1; i < n; i++)A[i] = A[i + 1], B[i] = B[i + 1];
	A[n] = ta, B[n] = tb;
}

long long int solve(int N, int k, int *a, int *b) {
	int i;
	n = N, K = k;
	for (i = 1; i <= n; i++)A[i] = a[i - 1], B[i] = b[i - 1];
	for (i = 0; i < K; i++) {
		Do();
		Rotate();
	}
	for (i = 1; i <= n; i++)res -= B[i];
	return res;
}

Subtask #1

0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	376 KB	Output is correct
2	Correct	6 ms	552 KB	Output is correct
3	Incorrect	3 ms	552 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #2

0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	376 KB	Output is correct
2	Correct	6 ms	552 KB	Output is correct
3	Incorrect	3 ms	552 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #3

0 / 31.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	93 ms	16360 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #4

0 / 38.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	376 KB	Output is correct
2	Correct	6 ms	552 KB	Output is correct
3	Incorrect	3 ms	552 KB	Output isn't correct
4	Halted	0 ms	0 KB	-