Submission #707854

#	Time	Username	Problem	Language	Result	Execution time	Memory
707854		Cyanmond	Wiring (IOI17_wiring)	C++17	100 / 100	58 ms	15656 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>

using i64 = long long;
constexpr i64 inf64 = 1ll << 50;

void chmin(i64 &a, i64 b) {
	if (a > b) a = b;
}

i64 solve(std::vector<i64> r, std::vector<i64> b) {
	std::vector<std::pair<i64, bool>> points;
	for (const auto e : r) {
		points.push_back({e, true});
	}
	for (const auto e : b) {
		points.push_back({e, false});
	}
	std::sort(points.begin(), points.end());
	std::vector<std::vector<i64>> seqs;
	bool lastType = true;
	for (int i = 0; i < (int)points.size(); ++i) {
		if (i == 0 or lastType != points[i].second) {
			seqs.push_back({});
			lastType = points[i].second;
		}
		seqs.back().push_back(points[i].first);
	}
	
	const int S = (int)seqs.size();
	std::vector<i64> dp = {0};
	for (int x = 0; x < S; ++x) {
		const auto &seq = seqs[x];
		const int T = (int)seq.size();
		std::vector<i64> seqSum(T + 1);
		for (int i = 0; i < T; ++i) {
			seqSum[i + 1] = seq[i];
			seqSum[i + 1] += seqSum[i];
		}
		auto rangeSum = [&](int l, int r) {
			return seqSum[r] - seqSum[l];
		};
		std::vector<i64> updateMin(T + 1, inf64);
		for (int i = 0; i < std::min((int)dp.size(), T + 1); ++i) {
			const i64 u = dp[i] + rangeSum(0, i) - rangeSum(i, T);
			chmin(updateMin[T - i], u);
		}
		for (int i = 0; i < T; ++i) {
			chmin(updateMin[i + 1], updateMin[i] - seq[T - 1]);
		}
		if (x != S - 1) {
			while ((int)updateMin.size() <= (int)seqs[x + 1].size()) {
				updateMin.push_back(updateMin.back() - seq[T - 1]);
			}
			for (int i = (int)updateMin.size() - 2; i >= 0; --i) {
				chmin(updateMin[i], updateMin[i + 1] + seqs[x + 1][0]);
			}
		}
		dp = std::move(updateMin);
	}
	return dp[0];
}

long long min_total_length(std::vector<int> r, std::vector<int> b) {
	std::vector<i64> r64, b64;
	for (const auto e : r) {
		r64.push_back(e);
	}
	for (const auto e : b) {
		b64.push_back(e);
	}
	return solve(r64, b64);
}

• Subtask 1: 7 / 7
• Subtask 2: 13 / 13
• Subtask 3: 10 / 10
• Subtask 4: 25 / 25
• Subtask 5: 45 / 45