Submission #719329

#	Time	Username	Problem	Language	Result	Execution time	Memory
719329		rainboy	Homecoming (BOI18_homecoming)	C++17	100 / 100	175 ms	86720 KiB

homecoming

#include "homecoming.h"

#define N	2000000
#define INF	0x3f3f3f3f3f3f3f3fLL

long long max(long long a, long long b) { return a > b ? a : b; }

long long solve(int n, int k, int *aa, int *bb) {
	static long long pp[N * 2];
	int i;
	long long p, ans, x, y;

	for (i = 0, p = 0; i < n * 2; i++)
		pp[i] = p += bb[i % n];
	ans = 0;
	x = y = 0;
	for (i = 0; i < n; i++) {
		long long z = max(x, y - (i == 0 ? 0 : pp[i - 1]));

		ans = max(ans, z + aa[i] - (pp[i + k - 1] - (i == 0 ? 0 : pp[i - 1])));
		x = max(x, z + aa[i] - (pp[i + k - 1] - (i == 0 ? 0 : pp[i - 1])));
		y = max(y, z + aa[i] + (i == 0 ? 0 : pp[i - 1]));
	}
	x = y = -INF;
	for (i = 0; i < n; i++) {
		long long z = max(max(x, y - (i == 0 ? 0 : pp[i - 1])), -pp[i - 1]);

		ans = max(ans, z + aa[i] - (pp[n - 1] - (i == 0 ? 0 : pp[i - 1])));
		x = max(x, z + aa[i] - (pp[i + k - 1] - (i == 0 ? 0 : pp[i - 1])));
		y = max(y, z + aa[i] + (i == 0 ? 0 : pp[i - 1]));
	}
	return ans;
}

• Subtask 1: 13 / 13
• Subtask 2: 18 / 18
• Subtask 3: 31 / 31
• Subtask 4: 38 / 38