제출 #1138268

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1138268		vuavisao	Homecoming (BOI18_homecoming)	C++20	0 / 100	344 ms	63044 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);
	}
};


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

	auto get_cost = [&] (ll pos) -> ll {
		return cost[pos + k - 1] - cost[pos - 1];
	};
	vector<ll> dp(2 * n + 1, -INF);
	SegTree st(2 * n);
	for (ll i = 1; i <= 2 * n; ++i) {
		st.Update(i, INF); // remove inf
		dp[i] = profit[i] - get_cost(i);
		if (i > k) {
			st.Update(i - k, -cost[i - 1]);
		}
		Max_self(dp[i], st.Query(max(1ll, i - n + 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]);
		st.Update(i, dp[i] + cost[i + k - 1]);
	}
	
	ll res = 0;
	for (ll i = 1; i <= 2 * n; ++i) {
		Max_self(res, dp[i]);
	}
	return res;
}

#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