Submission #585040

#	Time	Username	Problem	Language	Result	Execution time	Memory
585040		cologne	Wiring (IOI17_wiring)	C++17	0 / 100	1 ms	288 KiB

wiring

#include "wiring.h"

#include <algorithm>
#include <climits>
#include <tuple>

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 + 1; i++)
		if (T[i] != T[i - 1])
			b.push_back(i);

	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: 0 / 13
• Subtask 3: 0 / 10
• Subtask 4: 0 / 25
• Subtask 5: 0 / 45