Submission #166537

#	Time	Username	Problem	Language	Result	Execution time	Memory
166537		Eae02	Wiring (IOI17_wiring)	C++14	100 / 100	78 ms	16504 KiB

wiring

#include "wiring.h"

#include <bits/stdc++.h>
#define all(x) begin(x),end(x)
using namespace std;
using ll = long long;

vector<pair<ll, bool>> nodes;

vector<ll> prevDiff, nextDiff;
vector<ll> costToNext, costToPrev;
vector<ll> dp;

ll min_total_length(std::vector<int> r, std::vector<int> b) {
	for (int x : r)
		nodes.emplace_back(x, true);
	for (int x : b)
		nodes.emplace_back(x, false);
	
	sort(all(nodes));
	
	prevDiff.resize(nodes.size(), -1);
	costToPrev.resize(nodes.size(), 0);
	for (ll i = 1; i < nodes.size(); i++) {
		if (nodes[i].second == nodes[i - 1].second) {
			prevDiff[i] = prevDiff[i - 1];
			if (prevDiff[i] != -1) {
				costToPrev[i] = costToPrev[i - 1] + nodes[i].first - nodes[prevDiff[i] + 1].first;
			}
		} else {
			prevDiff[i] = i - 1;
			costToPrev[i] = 0;
		}
	}
	
	nextDiff.resize(nodes.size() + 1, nodes.size());
	costToNext.resize(nodes.size());
	for (ll i = nodes.size() - 2; i >= 0; i--) {
		if (nodes[i].second == nodes[i + 1].second) {
			nextDiff[i] = nextDiff[i + 1];
			if (nextDiff[i] != nodes.size()) {
				costToNext[i] = costToNext[i + 1] + nodes[nextDiff[i]].first - nodes[i].first;
			}
		} else {
			nextDiff[i] = i + 1;
			costToNext[i] = nodes[i + 1].first - nodes[i].first;
		}
	}
	
	//for (ll x : costToNext)
	//	cout << x << " ";
	//cout << "\n";
	
	dp.resize(nodes.size() + 1, 0);
	vector<ll> bestAnsR(nodes.size());
	for (ll i = nodes.size() - 1; i >= 0; i--) {
		dp[i] = LLONG_MAX;
		
		if (nextDiff[i] != nodes.size()) { // match right
			ll dstToNext = nextDiff[i] - i;
			ll ilen = min(nextDiff[nextDiff[i]] - nextDiff[i], dstToNext);
			dp[i] = costToNext[i] + bestAnsR[nextDiff[i] + ilen - 1];
		}
		
		if (prevDiff[i] != -1) { // match left
			dp[i] = min(dp[i], dp[i + 1] + nodes[i].first - nodes[prevDiff[i]].first);
		}
		
		bestAnsR[i] = costToPrev[i] + dp[i + 1];
		if (i != 0 && nodes[i - 1].second != nodes[i].second) {
			for (ll r = i + 1; r < nextDiff[i]; r++) {
				bestAnsR[r] = min(bestAnsR[r - 1], bestAnsR[r]);
			}
		}
	}
	
	return dp[0];
}

Compilation message (stderr)

wiring.cpp: In function 'll min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:24:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (ll i = 1; i < nodes.size(); i++) {
                 ~~^~~~~~~~~~~~~~
wiring.cpp:41:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (nextDiff[i] != nodes.size()) {
wiring.cpp:59:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (nextDiff[i] != nodes.size()) { // match right

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