Submission #584965

#	Time	Username	Problem	Language	Result	Execution time	Memory
584965		cologne	Wiring (IOI17_wiring)	C++17	38 / 100	95 ms	10944 KiB

wiring

#include "wiring.h"

#include <climits>
#include <algorithm>

using namespace std;

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

	vector<pair<long long, bool>> V;
	for (auto x : r)
		V.emplace_back(x, 0);
	for (auto x : b)
		V.emplace_back(x, 1);

	V.emplace_back(-1, 0);

	sort(V.begin(), V.end());

	vector<int> nT(N + 1, N + 1), nF(N + 1, N + 1);
	for (int i = N; i > 0; --i)
	{
		if (i != N)
			nT[i] = nT[i + 1], nF[i] = nF[i + 1];
		if (V[i].second)
			nT[i] = i;
		else
			nF[i] = i;
	}
	vector<long long> S(N + 1);
	for (int i = 1; i <= N; i++)
		S[i] = S[i - 1] + V[i].first;

	vector<long long> D(N + 1, LLONG_MAX / 2);
	D[0] = 0;
	for (int i = 1; i <= N; i++)
	{
		bool init = V[i].second;
		int j = init ? nF[i] : nT[i];
		if (j == N + 1)
			break;

		//  i   j-1 j
		//  B ... B R
		D[j] = min(D[j], D[i - 1] + V[j].first * (j - i) - (S[j - 1] - S[i - 1]));

		if (j == N)
			continue;

		if (V[j].second == V[j + 1].second)
		{
			int k = init ? nT[j] : nF[j];
			//  i   j-1 j j+1 k-1
			//  B ... B R R ... R

			long long lft = V[j - 1].first * (j - i) - (S[j - 1] - S[i - 1]);
			long long rgt = S[k - 1] - S[j - 1] - V[j].first * (k - j);
			long long mid = max(j - i, k - j) * (V[j].first - V[j - 1].first);
			D[k - 1] = min(D[k - 1], D[i - 1] + lft + mid + rgt);

			if (k == N + 1)
				continue;

			// i  j-1 j j+1 k-1 k
			// B....B R R ... R B
			for (long long lw : {0LL, V[j].first - V[j - 1].first})
				for (long long rw : {0LL, V[k].first - V[k - 1].first})
				{
					int ok = j;
					int ng = k - 1;
					while (ok + 1 != ng)
					{
						int mi = (ok + ng) / 2;
						long long lcost = lw + (V[mi].first - V[j].first);
						long long rcost = rw + (V[k - 1].first - V[mi].first);
						if (lcost < rcost)
							ok = mi;
						else
							ng = mi;
					}
					// i  j-1 j j+1  ok
					// B....B R R ... R
					long long lft = V[j - 1].first * (j - i) - (S[j - 1] - S[i - 1]);
					long long rgt = S[ok] - S[j - 1] - V[j].first * (ok + 1 - j);
					long long mid = max(j - i, ok + 1 - j) * (V[j].first - V[j - 1].first);
					D[ok] = min(D[ok], D[i - 1] + lft + mid + rgt);
				}
		}
		else
		{
			int k = init ? nF[j + 1] : nT[j + 1];

			// i   j-1 j j+1 k-1
			// B ... B R B ... B
			long long lft = V[j].first * (j - i) - (S[j - 1] - S[i - 1]);
			long long rgt = (S[k - 1] - S[j]) - V[j].first * (k - j - 1);
			D[k - 1] = min(D[k - 1], D[i - 1] + lft + rgt);

			if (k == N + 1 || j + 1 == k - 1)
				continue;

			// i   j-1 j j+1 k-1 k
			// B ... B R B ... B R

			for (long long lw : {0LL})
				for (long long rw : {0LL, V[k].first - V[k - 1].first})
				{
					int ok = j + 1;
					int ng = k - 1;
					while (ok + 1 != ng)
					{
						int mi = (ok + ng) / 2;
						long long lcost = lw + (V[mi].first - V[j].first);
						long long rcost = rw + (V[k - 1].first - V[mi].first);
						if (lcost < rcost)
							ok = mi;
						else
							ng = mi;
					}
					// i  j-1 j j+1  ok
					// B....B R B ... B
					long long lft = V[j].first * (j - i) - (S[j - 1] - S[i - 1]);
					long long rgt = (S[ok] - S[j]) - V[j].first * (ok - j);
					D[ok] = min(D[ok], D[i - 1] + lft + rgt);
				}
		}
	}

	return D.back();
}

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