#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
const lint INF = 1e18;
struct wire {
lint x;
int id;
char color;
bool operator < (const wire &o) const {
return x < o.x;
}
};
vector<vector<lint>> memo;
vector<vector<lint>> cluster;
vector<lint> group_size_prefix(1), dist_prefix(1);
inline void precompute() {
group_size_prefix[0] = 0;
for (int i = 1; i < cluster.size(); i++) {
group_size_prefix.push_back(group_size_prefix.back() + cluster[i].size());
}
group_size_prefix.push_back(group_size_prefix.back());
dist_prefix[0] = 0;
for (int i = 1; i < cluster.size(); i++) {
for (auto j : cluster[i]) {
dist_prefix.push_back(dist_prefix.back() + j);
}
}
}
inline lint connect(int le, int ri) { // connect two points: le and ri
if (le <= 0) return INF;
lint res = 0;
res += dist_prefix[ri] - dist_prefix[ri - 1];
res -= dist_prefix[le] - dist_prefix[le - 1];
return res;
}
inline lint connect_all(int le, int mid, int ri) { // connect all points between le and ri, with mid as pivot (the last element of previous group)
if (le <= 0) return INF;
lint res = 0;
res += dist_prefix[ri] - dist_prefix[mid];
res -= dist_prefix[mid] - dist_prefix[le - 1];
return res;
}
inline int get_index(int group, lint prev) {
return group_size_prefix[group] - prev;
}
lint dp(int group, int previous_left) {
// cout << group << " " << previous_left << " " << "\n";
if (previous_left < 0) return INF;
if (memo[group][previous_left] != -1) return memo[group][previous_left];
lint &res = memo[group][previous_left];
if (group >= cluster.size()) {
if (group > 2 && previous_left > 0) res = dp(group, previous_left - 1) + connect(get_index(group - 2, 0), get_index(group - 1, previous_left - 1));
else res = 0;
return res;
}
res = INF;
/* connect leftmost unpaired point of previous group with leftmost popint of current group */
res = min(res, dp(group, previous_left - 1) + connect(get_index(group - 1, previous_left - 1), get_index(group - 1, -1)));
/* connect leftmost unpaired point of previous group with rightmost point of the group before it */
if (group > 2) res = min(res, dp(group, previous_left - 1) + connect(get_index(group - 2, 0), get_index(group - 1, previous_left - 1)));
/* connect all unpaired points in the previous group with the prefix of points in the current group */
res = min(res, dp(group + 1, cluster[group].size() - previous_left) +
connect_all(get_index(group - 1, previous_left - 1), get_index(group - 1, 0), get_index(group - 1, - previous_left)));
return res;
}
lint min_total_length(vector<int> r, vector<int> b) {
int N = r.size() + b.size();
vector<wire> all_wires(N), red, blue;
for (auto i : r) red.push_back({i + 1, -1, 'r'});
for (auto i : b) blue.push_back({i + 1, -1, 'b'});
merge(red.begin(), red.end(), blue.begin(), blue.end(), all_wires.begin());
for (int i = 0; i < N; i++) all_wires[i].id = i;
cluster.emplace_back();
cluster[0].emplace_back(0);
for (int i = 0; i < N; i++) {
int le = i;
while (i + 1 < N && all_wires[i + 1].color == all_wires[le].color) i++;
int ri = i;
cluster.emplace_back();
for (int j = le; j <= ri; j++) {
cluster.back().emplace_back(all_wires[j].x);
}
}
memo.resize(cluster.size() + 1);
for (int i = 1; i <= cluster.size(); i++) {
memo[i].assign(cluster[i - 1].size() + 1, -1);
}
precompute();
return dp(1, 0);
}
