#include "wiring.h" #include <bits/stdc++.h> using namespace std; #define ll long long #define pi pair<int, int> #define pl pair<ll, ll> #define vi vector<int> #define vl vector<ll> #define fi first #define se second #define pb push_back #define all(x) (x).begin(),(x).end() ll min_total_length(vi r, vi b) { vector<pl> k; for (int i=0; i<r.size(); i++) { k.pb({r[i],0}); } for (int i=0; i<b.size(); i++) { k.pb({b[i],1}); } sort(all(k)); int n=k.size(); vl dp(n+1,1e15); vl sum(n+1,0); dp[0]=0; int j=-1; for (int i=0; i<n; i++) { sum[i+1]=sum[i]+k[i].fi; if (j==-1 && k[i].se!=k[0].se) { j=i; } } dp[j+1]=k[j].fi*j-sum[j]; int lst=0,fst=j; for (int i=j+1; i<n; i++) { if (k[i].se!=k[i-1].se) { fst=i; lst=i-1; } dp[i+1]=dp[lst]+sum[i+1]-sum[fst]-k[fst].fi*(i+1-fst)+k[fst-1].fi*(fst-lst)-sum[fst]+sum[lst]+(k[fst].fi-k[fst-1].fi)*max(i+1-fst,fst-lst); while (lst>0 && k[lst-1].se==k[lst].se) { lst--; if (dp[lst]+sum[i+1]-sum[fst]-k[fst].fi*(i+1-fst)+k[fst-1].fi*(fst-lst)-sum[fst]+sum[lst]+(k[fst].fi-k[fst-1].fi)*max(i+1-fst,fst-lst)<=dp[i+1]) { dp[i+1]=dp[lst]+sum[i+1]-sum[fst]-k[fst].fi*(i+1-fst)+k[fst-1].fi*(fst-lst)-sum[fst]+sum[lst]+(k[fst].fi-k[fst-1].fi)*max(i+1-fst,fst-lst); } else { lst++; break; } } } return dp[n]; }