#include "wiring.h" #include <bits/stdc++.h> #define fst first #define snd second #define pb push_back #define SZ(x) (int)x.size() #define ALL(x) x.begin(),x.end() #define forn(i,a,b) for(int i = a; i<b;i++) #define mset(a,v) memset(a,v,sizeof(a)) #ifdef D #define debug(x) cout<<" (debug) "<<x #else #define debug(x) //nada #endif using namespace std; typedef long long ll; const int MAXN = 100000+5; const int MAXB = 10; #define INF ((ll)10000000000000000) ll dp[MAXN][MAXB]; ll tam[MAXN]; vector<vector<ll>> block; ll f(ll x, ll y){ ll &res = dp[x][y]; if(res!=-1) return res; if(x==SZ(block) && y==0) return 0; if(x==SZ(block)) return INF; if(y==tam[x]) return res=f(x+1,0); res=INF; ll aux = 0; forn(j,y,SZ(block[x])){ aux+=block[x].back()-block[x][j]; } debug("pre "<<x<<" "<<y<<" "<<aux<<'\n'); forn(i,1,tam[x+1]+1){ aux+=block[x+1][i-1]-block[x+1][0]; res=min(res,f(x+1,i)+aux+(block[x+1][0]-block[x].back())*(max(tam[x]-y,(ll)i))); debug(aux<<" "<<(block[x+1][0]-block[x].back())*(max(tam[x]-y,(ll)i))<<'\n'); debug(" --------- "<<x<<" "<<y<<" "<<res<<'\n'); } return res; } long long min_total_length(std::vector<int> r, std::vector<int> b) { mset(dp,-1); ll last = -1; sort(ALL(r)); sort(ALL(b)); reverse(ALL(r)); reverse(ALL(b)); while(!r.empty() || !b.empty()){ if(b.empty() || (!r.empty() &&r.back()<b.back())){ if(last!=0){ block.pb({}); last=0; } block.back().pb(r.back()); r.pop_back(); }else{ if(last!=1){ block.pb({}); last=1; } block.back().pb(b.back()); b.pop_back(); } } forn(i,0,SZ(block)) tam[i]=SZ(block[i]); tam[SZ(block)]=0; forn(i,0,SZ(block)){ debug("BLOCK "<<i<<'\n'); for(auto j:block[i]) debug(" "<<j); debug('\n'); } return f(0,0); }