Submission #1139636

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139636		vuavisao	Homecoming (BOI18_homecoming)	C++20	100 / 100	141 ms	78724 KiB

homecoming

#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;

template<typename Lhs, typename Rhs> bool Min_self(Lhs& lhs, Rhs rhs) { if(rhs < lhs) { lhs = rhs; return true; } return false; }
template<typename Lhs, typename Rhs> bool Max_self(Lhs& lhs, Rhs rhs) { if(rhs > lhs) { lhs = rhs; return true; } return false; }

using ll = long long;
const ll INF = 1'000'000'000'000'000'000;

ll brute_force(int n, int k, int *a, int *b) {
	vector<ll> profit(n + 1);
	vector<ll> cost(2 * n + 1);
	for (ll i = 1; i <= n; ++i) {
		profit[i] = a[i - 1];
	}

	auto get_cost = [&] (ll pos) -> ll {
		return cost[pos + k - 1] - cost[pos - 1];
	};


	vector<ll> dp(n + 1, -INF);
	
	auto get_cost_bonus = [&] (ll pos) -> ll {
		return dp[pos] + cost[pos + k - 1];
	};
	ll res = 0;
	for (ll first = 1; first <= k; ++first) {
		fill(dp.begin(), dp.end(), -INF);

		auto get_intersect = [&] (ll pos) -> ll {
			ll right_pos = pos + k - 1;
			if (right_pos <= n) return 0;
			right_pos -= n;
			ll right_first = first + k - 1;
			if (first <= right_pos && right_pos <= right_first) {
				return cost[right_pos] - cost[first - 1];
			}
			return 0;
		};

		for (ll i = 1; i <= n; ++i) {
			cost[i] = cost[i + n] = b[i - 1];
		}
		for (ll i = 1; i <= 2 * n; ++i) {
			cost[i] += cost[i - 1];
		}
		dp[first] = profit[first] - get_cost(first);
		for (ll i = 1; i <= n; ++i) {
			cost[i] = cost[i + n] = b[i - 1];
			if (first <= i && i <= first + k - 1) {
				cost[i] = cost[i + n] = 0;
			}
		}
		for (ll i = 1; i <= 2 * n; ++i) {
			cost[i] += cost[i - 1];
		}
		deque<ll> dq;
		dq.push_back(first);
		ll max_no_bonus = -INF;
		for (ll i = first + 1; i <= n; ++i) {
			while (!dq.empty() && dq.front() <= i - k) dq.pop_front();
			ll bonus = get_intersect(i);
			if (i - k >= first) {
				Max_self(max_no_bonus, dp[i - k]);
			}
			Max_self(dp[i], max_no_bonus - get_cost(i) + bonus);
			if (!dq.empty()) {
				Max_self(dp[i], get_cost_bonus(dq.front()) - cost[i + k - 1] + bonus);
			}
			dp[i] += profit[i];
			while (!dq.empty() && get_cost_bonus(dq.back()) <= get_cost_bonus(i)) {
				dq.pop_back();
			}
			dq.push_back(i);
		}
		Max_self(res, *max_element(dp.begin(), dp.end()));
	}

	for (ll i = 1; i <= n; ++i) {
		cost[i] = cost[i + n] = b[i - 1];
	}
	for (ll i = 1; i <= 2 * n; ++i) {
		cost[i] += cost[i - 1];
	}
	fill(dp.begin(), dp.end(), -INF);
	ll max_no_bonus = -INF;
	deque<ll> dq;
	for (ll i = 1; i <= n; ++i) {
		while (!dq.empty() && dq.front() <= i - k) dq.pop_front();
		dp[i] = -get_cost(i);
		if (i > k) {
			Max_self(max_no_bonus, dp[i - k]);
		}
		Max_self(dp[i], max_no_bonus - get_cost(i));
		if (!dq.empty()) {
			Max_self(dp[i], get_cost_bonus(dq.front()) - cost[i + k - 1]);
		}
		dp[i] += profit[i];
		while (!dq.empty() && get_cost_bonus(dq.back()) <= get_cost_bonus(i)) {
			dq.pop_back();
		}
		dq.push_back(i);
	}
	Max_self(res, *max_element(dp.begin(), dp.end()));
	return res;
}

ll solution(int n, int k, int *a, int *b) {
	ll res = 0;
	if (k == n) {
		Max_self(res, accumulate(a, a + n, 0ll) - accumulate(b, b + n, 0ll));
		return res;
	}
	// Nhận xét 1:
	// Nếu ta sử dụng i, j mà i + k <= j
	// thì rõ ràng từ i + 1 -> j - 1 đều nên được chọn hết

	// Nhận xét 2:
	// Nếu coi như không có giao điểm ngược mọi i + k - 1 > n đều phải mua
	// thì dp như thường
	// còn nếu đã có giao điểm ngược, tức chi phí bị giảm đi thay vì bị tính 2 lần
	// thì rõ ràng điểm đầu mút trái sẽ là trong khoảng [n - k + 2, n]
	// còn đầu mút phải sẽ là trong khoảng [1, k - 1]
	// Do đó theo nhận xét 1 thì mọi điểm ở giữa đều nên được mua
	// Hay nếu nó là lời giải tốt nhất thì kiểu gì 1 cũng được chọn
	// Mà khi 1 đã được chọn thì chỉ cần mua 1 điểm trong [n - k + 2, n] thì mọi điểm sau -> n sẽ free hết
	
	// Do đó ta chỉ cần dp chọn 1 và không chọn 1 (không chọn 1 thì tính như cost không có giao)
	// Còn chọn 1 thì từ điểm được chọn [n - k + 2, n] + 1 -> n đều được free hết

	// sử dụng lại brute nhưng first <= 1


	vector<ll> profit(n + 1);
	vector<ll> cost(2 * n + 1);
	for (ll i = 1; i <= n; ++i) {
		profit[i] = a[i - 1];
	}

	auto get_cost = [&] (ll pos) -> ll {
		return cost[pos + k - 1] - cost[pos - 1];
	};


	vector<ll> dp(n + 1, -INF);
	
	auto get_cost_bonus = [&] (ll pos) -> ll {
		return dp[pos] + cost[pos + k - 1];
	};
	for (ll first = 1; first <= 1; ++first) {
		fill(dp.begin(), dp.end(), -INF);

		auto get_intersect = [&] (ll pos) -> ll {
			ll right_pos = pos + k - 1;
			if (right_pos <= n) return 0;
			right_pos -= n;
			ll right_first = first + k - 1;
			if (first <= right_pos && right_pos <= right_first) {
				return cost[right_pos] - cost[first - 1];
			}
			return 0;
		};

		for (ll i = 1; i <= n; ++i) {
			cost[i] = cost[i + n] = b[i - 1];
		}
		for (ll i = 1; i <= 2 * n; ++i) {
			cost[i] += cost[i - 1];
		}
		dp[first] = profit[first] - get_cost(first);
		for (ll i = 1; i <= n; ++i) {
			cost[i] = cost[i + n] = b[i - 1];
			if (first <= i && i <= first + k - 1) {
				cost[i] = cost[i + n] = 0;
			}
		}
		for (ll i = 1; i <= 2 * n; ++i) {
			cost[i] += cost[i - 1];
		}
		deque<ll> dq;
		dq.push_back(first);
		ll max_no_bonus = -INF;
		for (ll i = first + 1; i <= n; ++i) {
			while (!dq.empty() && dq.front() <= i - k) dq.pop_front();
			ll bonus = get_intersect(i);
			if (i - k >= first) {
				Max_self(max_no_bonus, dp[i - k]);
			}
			Max_self(dp[i], max_no_bonus - get_cost(i) + bonus);
			if (!dq.empty()) {
				Max_self(dp[i], get_cost_bonus(dq.front()) - cost[i + k - 1] + bonus);
			}
			dp[i] += profit[i];
			while (!dq.empty() && get_cost_bonus(dq.back()) <= get_cost_bonus(i)) {
				dq.pop_back();
			}
			dq.push_back(i);
		}
		Max_self(res, *max_element(dp.begin(), dp.end()));
	}

	for (ll i = 1; i <= n; ++i) {
		cost[i] = cost[i + n] = b[i - 1];
	}
	for (ll i = 1; i <= 2 * n; ++i) {
		cost[i] += cost[i - 1];
	}
	fill(dp.begin(), dp.end(), -INF);
	ll max_no_bonus = -INF;
	deque<ll> dq;
	for (ll i = 1; i <= n; ++i) {
		while (!dq.empty() && dq.front() <= i - k) dq.pop_front();
		dp[i] = -get_cost(i);
		if (i > k) {
			Max_self(max_no_bonus, dp[i - k]);
		}
		Max_self(dp[i], max_no_bonus - get_cost(i));
		if (!dq.empty()) {
			Max_self(dp[i], get_cost_bonus(dq.front()) - cost[i + k - 1]);
		}
		dp[i] += profit[i];
		while (!dq.empty() && get_cost_bonus(dq.back()) <= get_cost_bonus(i)) {
			dq.pop_back();
		}
		dq.push_back(i);
	}
	Max_self(res, *max_element(dp.begin(), dp.end()));
	return res;
}

long long solve(int n, int k, int *a, int *b) {
	// return brute_force(n, k, a, b);
	return solution(n, k, a, b);
}

#ifdef LOCAL

int main() {
	int T; assert(scanf("%d", &T) == 1);
	for(int t = 0; t < T; t++) {
		int N, K; assert(scanf("%d%d", &N, &K) == 2);
		int *A = new int[N];
		int *B = new int[N];
		for(int i = 0; i < N; i++) assert(scanf("%d", &A[i]) == 1);
		for(int i = 0; i < N; i++) assert(scanf("%d", &B[i]) == 1);
		printf("%lld\n", solve(N, K, A, B));
		delete[] A;
		delete[] B;
	}
	return 0;
}

#endif

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