Submission #151957

#	Time	Username	Problem	Language	Result	Execution time	Memory
151957		atoiz	Homecoming (BOI18_homecoming)	C++14	44 / 100	136 ms	55528 KiB

homecoming

#include "homecoming.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

long long solve(int N, int K, int *A, int *B)
{
	if (K == 1) {
		long long ans = 0;
		for (int i = 0; i < N; ++i) ans += max(0, A[i] - B[i]);
		return ans;
	}

	static const long long INF = 1e17;

	long long ans = accumulate(A, A + N, 0) - accumulate(B, B + N, 0);
	if (ans < 0) ans = 0;

	vector<long long> total(N * 2, 0); total[0] = B[0];
	for (int i = 1; i < N * 2; ++i) total[i] = total[i - 1] + B[i % N];

	vector<vector<long long>> dp(2);

	dp[0].assign(N + 1, 0); dp[1].assign(N + 1, -INF);
	dp[1][0] = 0;
	for (int i = 1; i <= N; ++i) {
		dp[1][i] = dp[1][i - 1];
		if (i - K + 1 >= 0) dp[1][i] = max(dp[1][i], dp[0][i - K + 1] - total[i - 1] + (i - K >= 0 ? total[i - 1 - K + 1] : 0));
		dp[0][i] = max(dp[0][i - 1] + A[i - 1] - B[i - 1], dp[1][i]);
		ans = max(ans, dp[0][i] - total[i + K - 2] + total[i - 1]);
	}
	ans = max(ans, *max_element(dp[1].begin(), dp[1].end()));

	dp[0].assign(N + 1, 0); dp[1].assign(N + 1, -INF);
	dp[0][1] = A[0] - B[0];
	for (int i = 2; i <= N; ++i) {
		dp[1][i] = dp[1][i - 1];
		if (i - K + 1 >= 0) dp[1][i] = max(dp[1][i], dp[0][i - K + 1] - total[i - 1] + (i - K >= 0 ? total[i - 1 - K + 1] : 0));
		dp[0][i] = max(dp[0][i - 1] + A[i - 1] - B[i - 1], dp[1][i]);
	}
	ans = max(ans, *max_element(dp[1].begin(), dp[1].end()));
	ans = max(ans, dp[0][N]);

	return ans;
}

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