제출 #1139561

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1139561		vuavisao	Homecoming (BOI18_homecoming)	C++20	0 / 100	33 ms	23876 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;
	}
	vector<ll> position(n + 1);
	vector<ll> profit(n + 1);
	vector<ll> cost(2 * n + 1);

	ll no_bound = n - k + 1;
	ll pos = 1;
	for (ll i = no_bound + 1; i <= n; ++i, ++pos) {
		position[pos] = i;
	}
	for (ll i = 1; i <= no_bound; ++i, ++pos) {
		position[pos] = i;
	}

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

	vector<ll> dp(n + 1, -INF);

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

	auto get_cost_bonus = [&] (ll fake_pos) -> ll {
		return dp[fake_pos] + cost[fake_pos + k - 1];
	};

	auto intersect = [&] (ll bonus_fake_pos, ll current_fake_pos) -> bool {
		ll bonus_pos = position[bonus_fake_pos];
		ll current_pos = position[current_fake_pos];

		if (bonus_pos + k - 1 <= n) {
			return (bonus_pos <= current_pos && current_pos <= (bonus_pos + k - 1));
		}
		return (bonus_pos <= current_pos && current_pos <= n)
			|| (1 <= current_pos && current_pos <= (bonus_pos + k - 1 - n));
	};
	
	ll max_no_bonus = -INF;
	deque<ll> dq;
	for (ll i = 1, j = 1; i <= n; ++i) {
		while (!dq.empty() && !intersect(dq.front(), i)) dq.pop_front();
		dp[i] = -get_cost(i);
		// cerr << "Phase0: " << position[i] << ' ' << dp[i] << '\n';
		while (!intersect(j, i) && j < i) {
			Max_self(max_no_bonus, dp[j++]);
		}
		Max_self(dp[i], max_no_bonus - get_cost(i));
		// cerr << "Phase1: " << position[i] << ' ' << dp[i] << '\n';
		if (!dq.empty()) {
			Max_self(dp[i], get_cost_bonus(dq.front()) - cost[i + k - 1]);
			// cerr << get_cost_bonus(dq.front()) << '\n';
		}
		// cerr << "Phase2: " << position[i] << ' ' << dp[i] << '\n';
		dp[i] += profit[i];
		// cerr << position[i] << ' ' << dp[i] << '\n';
		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: 0 / 13
• Subtask 2: 0 / 18
• Subtask 3: 0 / 31
• Subtask 4: 0 / 38