#include "wiring.h" #include <bits/stdc++.h> using namespace std; #define forsn(i, s, n) for (int i = int(s); i < int(n); i++) #define forn(i, n) forsn(i, 0, n) #define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--) #define dforn(i, n) dforsn(i, 0, n) using vi = vector<int>; using ii = pair<int, int>; using vii = vector<ii>; using ll = long long; using ld = long double; using vll = vector<ll>; using vb = vector<bool>; using pll = pair<ll, ll>; #define sz(x) int(x.size()) #define all(x) begin(x), end(x) #define sum(x) accumulate(all(x), 0LL) #define pb push_back #define eb emplace_back #define fst first #define snd second const ll INF = 1e18; vector<vi> buildSegments(const vi &r, const vi &b) { vector<vi> g; bool last = false; const int n = sz(r), m = sz(b); int i = 0, j = 0; while (i < n || j < m) { if (j == m || (i < n && r[i] < b[j])) { if (g.empty() || last) g.eb(); g.back().pb(r[i++]), last = 0; } else { if (g.empty() || !last) g.eb(); g.back().pb(b[j++]), last = 1; } } return g; } vll calcDP(const vll &prev, const vi &a, const vi &b) { const int n = sz(a), m = sz(b); vll pref(n + 1), suff(n + 1); ll sum = 0, dist = b.front() - a.back(); forn(i, n + 1) { pref[i] = prev[n - i] + sum; suff[i] = pref[i] + i * dist; if (i < n) sum += a.back() - a[n - 1 - i]; } forsn(i, 1, n + 1) pref[i] = min(pref[i], pref[i - 1]); dforn(i, n) suff[i] = min(suff[i], suff[i + 1]); vll dp(m + 1); sum = 0; forn(i, m + 1) { dp[i] = pref[min(i, n)] + sum + i * dist; if (i <= n) dp[i] = min(dp[i], suff[i] + sum); if (i < m) sum += b[i] - b.front(); } return dp; } ll min_total_length(vi r, vi b) { vector<vi> g = buildSegments(r, b); assert(sz(g) >= 2); vll dp(sz(g[0]) + 1, INF); dp[0] = 0; forsn(i, 1, sz(g)) dp = calcDP(dp, g[i - 1], g[i]); return dp.back(); }