#include "wiring.h" #include <bits/stdc++.h> using namespace std; long long min_total_length(vector<int> r, vector<int> b) { int N = r.size() + b.size(); int ridx = 0, bidx = 0; vector<int> pos = {0}, col = {0}; while (ridx < r.size() || bidx < b.size()) { if (bidx == b.size()) { pos.push_back(r[ridx]); col.push_back(0); ridx++; } else if (ridx == r.size()) { pos.push_back(b[bidx]); col.push_back(1); bidx++; } else if (r[ridx] < b[bidx]) { pos.push_back(r[ridx]); col.push_back(0); ridx++; } else { pos.push_back(b[bidx]); col.push_back(1); bidx++; } } vector<pair<int, int>> seg; for (int i = 1; i <= N; ) { int j = i; while (j <= N && col[i] == col[j]) { j++; } seg.push_back(make_pair(i, j - 1)); i = j; } vector<long long> pre(N + 1); vector<long long> suf(N + 1); for (int i = 0; i < seg.size(); i++) { int lb = seg[i].first, rb = seg[i].second; for (int j = rb - 1; j >= lb; j--) { suf[j] = suf[j + 1] + (pos[rb] - pos[j]); } for (int j = lb + 1; j <= rb; j++) { pre[j] = pre[j - 1] + (pos[j] - pos[lb]); } } vector<long long> dp(N + 1, (long long)1e18); dp[0] = 0; for (int sid = 1; sid < seg.size(); sid++) { int clb = seg[sid].first, crb = seg[sid].second; int plb = seg[sid - 1].first, prb = seg[sid - 1].second; for (int c = clb; c <= crb; c++) { for (int p = plb; p <= prb; p++) { int psz = prb - p + 1; int csz = c - clb + 1; long long cost = 0; cost += suf[p] + pre[c]; cost += (pos[clb] - pos[prb]) * max(psz, csz); dp[c] = min(dp[c], min(dp[p - 1], dp[p]) + cost); if (p == 1) { break; } } } } return dp[N]; }