제출 #585046

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
585046		cologne	전선 연결 (IOI17_wiring)	C++17	13 / 100	43 ms	7808 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;
	}
	return D.back();
}

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