Submission #574241

#	Time	Username	Problem	Language	Result	Execution time	Memory
574241		KoD	Wiring (IOI17_wiring)	C++17	13 / 100	42 ms	9764 KiB

wiring

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

using ll = long long;

using std::vector;
using std::array;
using std::pair;
using std::tuple;

template <class T>
constexpr T infty = std::numeric_limits<T>::max() / 2;

ll min_total_length(vector<int> A, vector<int> B) {
	int ai = 0, bi = 0;
	vector<int> left;
	vector<ll> dp;
	while (ai < (int)A.size() or bi < (int)B.size()) {
		if (ai == (int)A.size() or (bi < (int)B.size() and A[ai] > B[bi])) {
			std::swap(A, B);
			std::swap(ai, bi);
		}
		vector<int> right;
		while (ai < (int)A.size() and (bi == (int)B.size() or A[ai] < B[bi])) {
			right.push_back(A[ai]);
			ai += 1;
		}
		const int lsz = (int)left.size();
		const int rsz = (int)right.size();
		if (lsz == 0) {
			left = std::move(right);
			dp.resize(rsz + 1, infty<ll>);
			dp[rsz] = 0;
			continue;
		}
		vector<ll> lsum(lsz + 1);
		for (int i = 0; i < lsz; ++i) {
			lsum[i + 1] = lsum[i] + (left[lsz - 1] - left[lsz - i - 1]);
		}
		vector<ll> rsum(rsz + 1);
		for (int i = 0; i < rsz; ++i) {
			rsum[i + 1] = rsum[i] + (right[i] - right[0]);
		}
		const ll between = right[0] - left[lsz - 1];
		vector<ll> pre1(lsz + 1), pre2(lsz + 1);
		for (int l = 1; l <= lsz; ++l) {
			pre1[l] = dp[l] + lsum[l];
			pre2[l] = dp[l] + lsum[l] + between * l;
		}
		for (int l = 2; l <= lsz; ++l) {
			pre1[l] = std::min(pre1[l], pre1[l - 1]);
		}
		for (int l = lsz - 1; l >= 1; --l) {
			pre2[l] = std::min(pre2[l], pre2[l + 1]);
		}
		vector<ll> next(rsz + 1);
		next[0] = dp[0];
		for (int r = 1; r <= rsz; ++r) {
			// 1 <= l <= r : dp[l] + lsum[l] + rsum[r] + between * r 
			// r <= l      : dp[l] + lsum[l] + rsum[r] + between * l
			if (r <= lsz) {
				next[r] = std::min(pre1[r] + rsum[r] + between * r, pre2[r] + rsum[r]);
			} else {
				next[r] = pre1[lsz] + rsum[r] + between * r;
			}
		}
		left = std::move(right);
		dp.resize(rsz + 1);
		for (int i = 0; i <= rsz; ++i) {
			dp[rsz - i] = next[i];
		}
	}
	return dp[0];
}

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