#include "wiring.h" #include <bits/stdc++.h> using namespace std; long long min_total_length(std::vector<int> R, std::vector<int> B) { int n = R.size(), m = B.size(); vector<long long> r = {0}, b = {0}; for (int i : R) r.push_back(i + r.back()); for (int i : B) b.push_back(i + b.back()); vector<pair<int, long long>> p; for (int i = 0; i < n; i++) p.emplace_back(R[i], i + 1); for (int i = 0; i < m; i++) p.emplace_back(B[i], -i - 1); sort(p.begin(), p.end()); vector<int> head(n + m); auto get = [&](int s, int e) { if (p[s].second > 0) { long long lr = p[s].second - 1; long long rr = p[head[e] - 1].second - 1; long long lb = -p[head[e]].second - 1; long long rb = -p[e].second - 1; //cout << lr << ' ' << rr << ' ' << lb << ' ' << rb << '\n'; return (rr - lr + 1) * R[rr] - r[rr + 1] + r[lr] + b[rb + 1] - b[lb] - (rb - lb + 1) * B[lb] + max(rr - lr + 1, rb - lb + 1) * (B[lb] - R[rr]); } else { long long lb = -p[s].second - 1; long long rb = -p[head[e] - 1].second - 1; long long lr = p[head[e]].second - 1; long long rr = p[e].second - 1; //cout << lr << ' ' << rr << ' ' << lb << ' ' << rb << '\n'; return (rb - lb + 1) * B[rb] - b[rb + 1] + b[lb] + r[rr + 1] - r[lr] - (rr - lr + 1) * R[lr] + max(rr - lr + 1, rb - lb + 1) * (R[lr] - B[rb]); } }; long long inf = 1e18; vector<long long> dp(n + m + 1, inf); dp[0] = 0; for (int i = 1; i < n + m; i++) { head[i] = head[i - 1]; if (p[i].second * p[i - 1].second < 0) { int prev = head[i]; head[i] = i; dp[i + 1] = dp[i] + get(i - 1, i); for (int j = prev; j < i; j++) { dp[i + 1] = min(dp[i + 1], dp[j] + get(j, i)); } } else if (head[i]) { int s = head[head[i] - 1], e = head[i]; if (s == 0) dp[i + 1] = get(0, i); else if (e - s < 200) { for (int j =s; j < e; j++) { dp[i + 1] = min(dp[i + 1], min(dp[j], dp[j + 1]) + get(j, i)); } } else { int low = s, high = e; while (high - low > 1) { int mid = (low + high) / 2; if (dp[mid] + get(mid, i) <= dp[mid - 1] + get(mid - 1, i)) low = mid; else high = mid; } dp[i + 1] = dp[low] + get(low, i); } } } return dp[n + m]; }