#include "wiring.h" #include <bits/stdc++.h> #define fst first #define snd second #define pb push_back #define SZ(x) (long long)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 = 200000+5; #define INF ((ll)10000000000000000) ll dp[MAXN]; ll n,m; ll mypos[MAXN]; ll mycolor[MAXN]; ll myblock[MAXN]; ll myposblock[MAXN]; vector<vector<ll>> block; long long min_total_length(std::vector<int> r, std::vector<int> b) { mset(dp,-1); ll cnt = 0; 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; } mypos[cnt]=r.back(); mycolor[cnt]=0; myblock[cnt]=SZ(block)-1; myposblock[cnt]=SZ(block.back()); block.back().pb(cnt); //block.back().pb(r.back()); r.pop_back(); cnt++; }else{ if(last!=1){ block.pb({}); last=1; } mypos[cnt]=b.back(); mycolor[cnt]=0; myblock[cnt]=SZ(block)-1; myposblock[cnt]=SZ(block.back()); block.back().pb(cnt); //block.back().pb(b.back()); b.pop_back(); cnt++; } } forn(i,0,SZ(block)){ debug("BLOCK "<<i<<'\n'); for(auto j:block[i]) debug(" "<<j); debug('\n'); } vector<vector<ll>> pre(SZ(block)); vector<vector<ll>> suf(SZ(block)); forn(i,0,SZ(block)){ pre[i].clear(); pre[i].resize(SZ(block[i])); forn(j,0,SZ(block[i])){ pre[i][j]=mypos[block[i][j]]-mypos[block[i][0]]; if(j>0) pre[i][j]+=pre[i][j-1]; } suf[i].clear(); suf[i].resize(SZ(block[i])); for(int j = SZ(block[i])-1; j>=0; j--){ suf[i][j]=mypos[block[i].back()]-mypos[block[i][j]]; if(j+1<SZ(block[i])) suf[i][j]+=suf[i][j+1]; } } forn(i,0,SZ(block)){ debug("Block "<<i<<'\n'); for(auto j:pre[i]){ debug(j<<" "); } debug('\n'); for(auto j:suf[i]){ debug(j<<" "); } debug('\n'); debug('\n'); } for(int i = 0; i<cnt; i++){ dp[i]=INF; } vector<ll> preff; vector<ll> suff; for(int i = 0; i<cnt; i++){ if(myblock[i]-1>=0){ /* forn(j,0,SZ(block[myblock[i]-1])){ ll ib = myblock[i]; ll ni = block[ myblock[i]-1 ][j]; ll cost = mypos[ block[ ib ][0] ] - mypos[ block[ ib-1 ].back() ]; ll maxi = max(SZ(block[ib-1])-(j+1) , myposblock[i]+1); dp[i]=min(dp[i],dp[ni] + pre[ib][myposblock[i]] + suf[ib-1][j+1] + cost * maxi); }*/ ll ruse = myposblock[i]+1; ll ib = myblock[i]; ll cost = mypos[ block[ ib ][0] ] - mypos[ block[ ib-1 ].back() ]; /*cout<<SZ(block[ib-1])-ruse<< " ind suff\n"; cout<<suff[ max((ll)0, SZ(block[ib-1]) - ruse ) ] + cost * ruse + pre[ib][ruse-1]<<'\n'; cout<<(ruse>=SZ(preff)?INF:preff[ SZ(block[ib-1]) - ruse ]) + pre[ib][ruse-1]<<'\n';*/ dp[i]=min(dp[i], suff[ max((ll)0, SZ(block[ib-1]) - (ruse+1) ) ] + cost * ruse + pre[ib][ruse-1] ); dp[i]=min(dp[i], (ruse>=SZ(preff)?INF:preff[ SZ(block[ib-1]) - (ruse+1) ]) + pre[ib][ruse-1] ); if(myblock[i]-2 == -1){ ll ib = myblock[i]; ll cost = mypos[ block[ ib ][0] ] - mypos[ block[ ib-1 ].back() ]; ll maxi = max(SZ(block[ib-1]) , myposblock[i]+1); dp[i]=min(dp[i], pre[ib][myposblock[i]] + suf[ib-1][0] + cost * maxi); //cout<<i<<" cae aca\n"; }else if(myblock[i]-2>=0){ ll ib = myblock[i]; ll cost = mypos[ block[ ib ][0] ] - mypos[ block[ ib-1 ].back() ]; ll maxi = max(SZ(block[ib-1]) , myposblock[i]+1); ll ni = block[myblock[i]-2].back(); dp[i]=min(dp[i],dp[ni] + pre[ib][myposblock[i]] + suf[ib-1][0] + cost * maxi); } } if(myposblock[i]==SZ(block[myblock[i]])-1 && myblock[i]+1<SZ(block)){ preff.clear(); suff.clear(); ll ib = myblock[i]; ll cost = mypos[ block[ ib+1 ][0] ] - mypos[ block[ ib ].back() ]; forn(j,0,SZ(block[myblock[i]])){ preff.pb(dp[block[ib][j]]+cost*(SZ(block[ib])-(j+1))+(j+1<SZ(suf[ib])?suf[ib][j+1]:0)); if(j>0) preff.back()=min(preff.back(), preff[j-1]); } forn(j,0,SZ(suf[ib])){ suff.pb(dp[block[ib][j]]+(j+1<SZ(suf[ib])?suf[ib][j+1]:0)); } for(int j = SZ(block[ib])-1; j>=0; j--){ if(j+1<SZ(block[ib])) suff[j]=min(suff[j],suff[j]); } debug("new \n"); debug("preff ");for(auto j:preff) debug(j<<" "); debug("\n"); debug("suff ");for(auto j:suff) debug(j<<" "); debug("\n"); } debug("dp "<<i<<" "<<dp[i]<<'\n'); } return dp[cnt-1]; }