Submission #1138566

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138566		vuavisao	Homecoming (BOI18_homecoming)	C++20	0 / 100	1097 ms	35440 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;

struct SegTree {
	struct Node {
		ll val = -INF;
		Node() {};
		Node(ll _val) : val(_val) {};
		Node operator+(const Node& other) const {
			Node res;
			res.val = max(this->val, other.val);
			return res;
		}
	};

	ll n_node = 0;
	vector<Node> tree;

	void resize(ll n) { n_node = n; tree.resize((n_node << 2) + 10); }
	SegTree() {};
	SegTree(ll n) { this->resize(n); }

	void update(ll node, ll l, ll r, ll idx, ll val) {
		if (l == r) {
			tree[node].val += val;
			return;
		}
		ll mid = (l + r) >> 1;
		if (idx <= mid) update(node << 1, l, mid, idx, val);
		else update(node << 1 | 1, mid + 1, r, idx, val);
		tree[node] = tree[node << 1] + tree[node << 1 | 1];
	}

	void Update(ll idx, ll val) {
		return update(1, 1, n_node, idx, val);
	}

	Node query(ll node, ll l, ll r, ll L, ll R) {
		if (L <= l && r <= R) return tree[node];
		ll mid = (l + r) >> 1;
		if (R <= mid) return query(node << 1, l, mid, L, R);
		if (L > mid) return query(node << 1 | 1, mid + 1, r, L, R);
		return query(node << 1, l, mid, L, R) + query(node << 1 | 1, mid + 1, r, L, R);
	}

	Node Query(ll l, ll r) {
		if (l > r) return Node();
		return query(1, 1, n_node, l, r);
	}
};

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];
		cost[i] = cost[i + n] = b[i - 1];
	}
	for (ll i = 1; i <= 2 * n; ++i) {
		cost[i] += cost[i - 1];
	}

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

	vector<ll> dp(n + 1, -INF);
	SegTree st(n);
	ll res = 0;
	for (ll first = 1; first <= k; ++first) {
		fill(dp.begin(), dp.end(), -INF);
		fill(st.tree.begin(), st.tree.end(), SegTree::Node());

		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;
		};

		dp[first] = profit[first] - get_cost(first);
		st.Update(first, INF); // remove inf
		st.Update(first, dp[first] + cost[first + k - 1]);
		for (ll i = first + 1; i <= n; ++i) {
			st.Update(i, INF); // remove inf
			
			ll bonus = get_intersect(i);
			if (i - k >= first) {
				st.Update(i - k, -cost[i - 1]);
			}
			Max_self(dp[i], st.Query(first, i - k).val - get_cost(i) + bonus);
			Max_self(dp[i], st.Query(max(first, i - k + 1), i - 1).val - cost[i + k - 1] + bonus);
			dp[i] += profit[i];
			st.Update(i, dp[i] + cost[i + k - 1]);
		}
		Max_self(res, *max_element(dp.begin(), dp.end()));
	}

	fill(dp.begin(), dp.end(), -INF);
	fill(st.tree.begin(), st.tree.end(), SegTree::Node());
	for (ll i = 1; i <= n; ++i) {
		st.Update(i, INF); // remove inf
		dp[i] = -get_cost(i);
		if (i > k) {
			st.Update(i - k, -cost[i - 1]);
		}
		Max_self(dp[i], st.Query(1, i - k).val - get_cost(i));
		Max_self(dp[i], st.Query(max(1ll, i - k + 1), i - 1).val - cost[i + k - 1]);
		dp[i] += profit[i];
		st.Update(i, dp[i] + cost[i + k - 1]);
		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);
}

#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