#include <bits/stdc++.h> #define L(i, j, k) for(int i = (j); i <= (k); i++) #define R(i, j, k) for(int i = (j); i >= (k); i--) #define ll long long #define sz(a) ((int) a.size()) #define all(a) a.begin(), a.end() #define vi vector<ll> #define pb emplace_back #define me(a, x) memset(a, x, sizeof(a)) #define fst first #define snd second #define ii pair<ll, ll> using namespace std; const int N=1e5+5; const ll inf=1e18; void chmin(ll &a,ll b){ a=min(a,b); } long long min_total_length(std::vector<int> r, std::vector<int> b) { int n=sz(r),m=sz(b); vector<ii> points; L(i,0,n-1){ points.pb(r[i],1); } L(i,0,m-1){ points.pb(b[i],0); } sort(all(points)); int nn=sz(points); vector<vi>blk; vi ar; int lst=points[0].snd; L(i,0,nn-1){ if(lst!=points[i].snd){ blk.pb(ar); ar.clear(); lst^=1; } ar.pb(points[i].fst); } blk.pb(ar); vector<vi>dp(sz(blk)); dp[0].resize(sz(blk[0])+1,0); L(i,1,sz(blk)-1){ dp[i].resize(sz(blk[i])+1,inf); ll diff=blk[i][0]-blk[i-1].back(),pf=0; dp[i][0]=dp[i-1].back(); L(r,0,sz(blk[i])-1){ pf+=blk[i][r]-blk[i][0]; if(i==1){ ll sf = 0; R(l,sz(blk[i-1])-1,0)sf+=blk[i-1].back()-blk[i-1][l]; chmin(dp[i][r+1],max(sz(blk[i-1]),r+1)*diff+pf+sf); //conecto todos los de atras conmigo continue; } ll sf=0; R(l,sz(blk[i-1])-1,0){ sf+=blk[i-1].back()-blk[i-1][l]; chmin(dp[i][r+1],dp[i-1][l]+max(sz(blk[i-1])-l,r+1)*diff+pf+sf); } } } //~ L(i,0,sz(dp)-1){ //~ cout<<"============="<<endl; //~ L(j,0,sz(dp[i])-1){ //~ cout<<dp[i][j]<<" "; //~ } //~ cout<<endl; //~ } return dp.back().back(); }