제출 #584960

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
584960		cologne	전선 연결 (IOI17_wiring)	C++17	13 / 100	48 ms	9664 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++)
	{
		// cerr << i << " " << V[i].first << " " << (V[i].second ? 'T' : 'F') << endl;
		bool init = V[i].second;
		int j = init ? nF[i] : nT[i];
		if (j == N + 1)
			break;

		// cout << "[" << i << ", " << j << "]: " << V[j].first * (j - i) - (S[j - 1] - S[i - 1]) << endl;
		D[j] = min(D[j], D[i - 1] + V[j].first * (j - i) - (S[j - 1] - S[i - 1]));
		// cout << "D[" << j << "] = " << D[j] << endl;

		if (j == N)
			continue;

		if (V[j].second == V[j + 1].second)
		{
			int k = init ? nT[j] : nF[j];
			// cerr << i << " " << j << "==" << j + 1 << " " << k << endl;
			//  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);
			// cout << "[" << i << ", " << k - 1 << "]: " << lft + mid + rgt << endl;
			D[k - 1] = min(D[k - 1], D[i - 1] + lft + mid + rgt);
			// cout << "D[" << k - 1 << "] = " << D[k - 1] << endl;

			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 - 1] - S[j - 1] - V[j].first * (ok - j);
					long long mid = max(j - i, ok - 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];
			// cout << i << " " << j << "!=" << j + 1 << " " << k << endl;

			// 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 - 1]) - V[j].first * (k - j);
			// cout << "[" << i << ", " << k - 1 << "]: " << lft + rgt << endl;
			D[k - 1] = min(D[k - 1], D[i - 1] + lft + rgt);
			// cout << "D[" << k - 1 << "] = " << D[k - 1] << endl;

			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 - 1].first - V[i - 1].first) - S[j] * (j - i);
					long long rgt = (V[ok - 1].first - V[j - 1].first) - S[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: 0 / 25
• Subtask 5: 0 / 45