제출 #584918

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
584918		cologne	전선 연결 (IOI17_wiring)	C++17	30 / 100	1084 ms	7408 KiB

wiring

#include "wiring.h"

#include <climits>
#include <algorithm>
using namespace std;

bool is_st2(vector<int> r, vector<int> b)
{
	return r.back() < b.front();
}

long long solve_st2(vector<int> r, vector<int> b)
{
	long ans = 0;
	for (int x : r)
		ans += r.back() - x;
	for (int y : b)
		ans += y - b.front();
	ans += max(r.size(), b.size()) * (b.front() - r.back());

	return ans;
}

long long min_total_length(vector<int> r, vector<int> b)
{
	if (is_st2(r, b))
		return solve_st2(r, b);

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

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

	vector<long long> D(V.size() + 1, LLONG_MAX / 2);
	D[0] = 0;
	for (int i = 0; i < (int)V.size(); i++)
	{
		bool colour = V[i].second;
		long long rsum = V[i].first, rcnt = 1, mid = -1;

		int j;
		for (j = i - 1; j >= 0; --j)
		{
			if (colour != V[j].second)
			{
				rsum -= rcnt * V[j + 1].first;
				mid = V[j + 1].first - V[j].first;
				D[i + 1] = min(D[i + 1], D[j] + mid * rcnt + rsum);
				break;
			}
			else
			{
				rcnt++;
				rsum += V[j].first;
			}
		}
		if (j <= 0)
			continue;
		int anchor = V[j].first;

		if (V[j - 1].second == colour)
		{
			for (--j; j >= 0; --j)
			{
				if (V[j].second != colour)
					break;

				rsum += anchor - V[j].first;
				D[i + 1] = min(D[i + 1], D[j] + mid * rcnt + rsum);
			}
		}
		else
		{
			long long bsum = V[j].first, bcnt = 1;
			for (--j; j >= 0; --j)
			{
				if (V[j].second == colour)
					break;
				bsum += V[j].first;
				bcnt++;

				long long cost = (anchor * bcnt - bsum) + rsum + mid * max(rcnt, bcnt);
				D[i + 1] = min(D[i + 1], D[j] + cost);
			}
		}
	}

	return D.back();
}

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