Submission #585072

#	Time	Username	Problem	Language	Result	Execution time	Memory
585072		cologne	Wiring (IOI17_wiring)	C++17	100 / 100	56 ms	11740 KiB

wiring

#include "wiring.h"

#include <algorithm>
#include <climits>

using namespace std;

long long min_total_length(vector<int> _r, vector<int> _b)
{
	int N = _r.size() + _b.size();

	vector<long long> V(N + 1);
	vector<bool> T(N + 1);
	{
		vector<pair<long long, bool>> X;
		for (auto x : _r)
			X.emplace_back(x, 0);
		for (auto x : _b)
			X.emplace_back(x, 1);
		sort(X.begin(), X.end());
		for (int i = 0; i < N; i++)
			V[i + 1] = X[i].first, T[i + 1] = X[i].second;
	}

	// [block[i], block[i+1])
	vector<int> b = {1};
	for (int i = 2; i <= N; i++)
		if (T[i] != T[i - 1])
			b.push_back(i);
	b.push_back(N + 1);

	vector<long long> S(N + 1);
	for (int i = 1; i <= N; i++)
		S[i] = S[i - 1] + V[i];

	vector<long long> D(N + 1, LLONG_MAX / 2);

	D[0] = 0;
	for (int i = b[1]; i < b[2]; i++)
	{
		long long lft = V[b[1] - 1] * (b[1] - b[0]) - (S[b[1] - 1] - S[b[0] - 1]);
		long long rgt = (S[i] - S[b[1] - 1]) - V[b[1]] * (i - (b[1] - 1));
		long long mid = max(i - (b[1] - 1), b[1] - b[0]) * (V[b[1]] - V[b[1] - 1]);
		D[i] = lft + rgt + mid;
	}

	vector<long long> A(N + 1), B(N + 1);

	for (int idx = 2; idx < (int)b.size() - 1; idx++)
	{
		int pps = b[idx - 2], ppe = b[idx - 1] - 1;
		int ps = b[idx - 1], pe = b[idx] - 1;
		int s = b[idx], e = b[idx + 1] - 1;

		if (ps == pe)
		{
			long long lmin = D[ppe];
			long long lsum = 0;
			for (int i = ppe; i >= pps; --i)
			{
				lsum += V[ps] - V[i];
				lmin = min(lmin, D[i - 1] + lsum);
			}
			long long rsum = 0;
			for (int i = s; i <= e; i++)
			{
				rsum += V[i] - V[pe];
				D[i] = lmin + rsum;
			}
		}
		else
		{
			for (int i = ps; i <= pe; i++)
			{
				A[i] = D[i - 1] + V[pe] * (pe - i + 1) - (S[pe] - S[i - 1]);
				B[i] = A[i] + (pe - i + 1) * (V[s] - V[pe]);
			}
			for (int i = pe - 1; i >= ps; i--)
				A[i] = min(A[i], A[i + 1]);
			for (int i = ps + 1; i <= pe; i++)
				B[i] = min(B[i], B[i - 1]);

			long long rgt = 0;
			for (int i = s; i <= e; i++)
			{
				rgt += V[i] - V[s];
				D[i] = A[max(ps, pe - (i - s))] + (i - s + 1) * (V[s] - V[pe]) + rgt;
				if (pe - (i - s) >= ps)
					D[i] = min(D[i], B[pe - (i - s)] + rgt);
			}
		}
	}

	return D.back();
}

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