Submission #166533

#	Time	Username	Problem	Language	Result	Execution time	Memory
166533		Eae02	Wiring (IOI17_wiring)	C++14	30 / 100	1049 ms	19300 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> memo;
ll dp(ll i) {
	if (i >= memo.size())
		return 0;
	if (memo[i] != -1)
		return memo[i];
	
	ll ans = LLONG_MAX;
	
	if (nextDiff[i] != nodes.size()) { // match right
		ll dstToNext = nextDiff[i] - i;
		ll ilen = min(nextDiff[nextDiff[i]] - nextDiff[i], dstToNext);
		
		for (ll r = 0; r < ilen; r++) {
			ll cost = costToNext[i] + costToPrev[nextDiff[i] + r];
			ans = min(ans, cost + dp(nextDiff[i] + r + 1));
		}
	}
	
	if (prevDiff[i] != -1) { // match left
		ans = min(ans, dp(i + 1) + nodes[i].first - nodes[prevDiff[i]].first);
	}
	
	return memo[i] = ans;
}

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";
	
	memo.resize(nodes.size(), -1);
	
	return dp(0);
}

Compilation message (stderr)

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

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