#include "wiring.h" #include <bits/stdc++.h> using namespace std; using ll = long long; using pii = pair<ll,ll>; const ll INF = 1e18; ll min_total_length(vector<int> r, vector<int> b) { vector<pii> v0; for (ll x: r) { v0.push_back({x,0}); } for (ll x: b) { v0.push_back({x,1}); } sort(v0.begin(),v0.end()); ll N = v0.size(); vector<ll> dist0(N,INF),dist1(N,INF); //min distance from 0 or 1 ll x0max = -INF; ll x1max=-INF; for (ll i=0;i<N;i++) { pii p0 = v0[i]; if (p0.second==0) { x0max = p0.first; } else { x1max = p0.first; } dist0[i]=min(dist0[i],p0.first-x0max); dist1[i]=min(dist1[i],p0.first-x1max); } ll x0min = INF; ll x1min=INF; for (ll i=(N-1);i>=0;i--) { pii p0 = v0[i]; if (p0.second==0) { x0min = p0.first; } else { x1min = p0.first; } dist0[i]=min(dist0[i],-p0.first+x0min); dist1[i]=min(dist1[i],-p0.first+x1min); } vector<pii> dpt[N]; //dp transition: (final x, value) //initial/final x: # of things already processed for (ll i=0;i<N;i++) { pii p0 = v0[i]; if (p0.second==0) { dpt[i].push_back({i+1,dist1[i]}); } else { dpt[i].push_back({i+1,dist0[i]}); } } for (ll x=0;x<(N-1);x++) { ll fval = 0; ll yc = 0; while ((x-yc)>=0 && (x+1+yc)<N && v0[x-yc].second==0 && v0[x+yc+1].second==1) { fval += v0[x+yc+1].first - v0[x-yc].first; dpt[x-yc].push_back({x+yc+2,fval}); yc++; } fval = 0; yc = 0; while ((x-yc)>=0 && (x+1+yc)<N && v0[x-yc].second==1 && v0[x+yc+1].second==0) { fval += v0[x+yc+1].first - v0[x-yc].first; dpt[x-yc].push_back({x+yc+2,fval}); yc++; } } vector<ll> dp(N+1,INF); dp[0]=0; for (ll x=0;x<N;x++) { for (pii p0: dpt[x]) { dp[p0.first]=min(dp[p0.first],dp[x]+p0.second); } } return dp[N]; }