#include "wiring.h"
#include <iostream>
#define MAX 1000000000000000000
using namespace std;
typedef long long ll;
ll abs(ll x) {
return x>=0 ? x:-x;
}
bool isSub1(int rSize, int bSize) {
return rSize<=200 && bSize<=200;
}
ll sub1Dp[210][210]; // sub1Dp[i][j]: minCost when connecting r[0~i], b[0~j]
ll sub1(vector<int> &r, vector<int> &b) {
int n = r.size(), m = b.size();
sub1Dp[0][0] = abs(r[0] - b[0]);
for(int j=1; j<m; j++) {
sub1Dp[0][j] = sub1Dp[0][j-1] + abs(r[0] - b[j]);
}
for(int i=1; i<n; i++) {
sub1Dp[i][0] = sub1Dp[i-1][0] + abs(r[i] - b[0]);
for(int j=1; j<m; j++) {
// r[i], b[j] should be connected
ll connectingCost = abs(r[i] - b[j]);
// case 1: r[i], b[j] are seperated to the rest
ll t = sub1Dp[i-1][j-1]; // t is the restCost
// case 2: r[i] is connected to the rest
// in this case, b[j] is seperated to the rest
t = min(t, sub1Dp[i][j-1]);
// case 3: b[j] is connected to the rest
// in this case, r[i] is seperated to the rest
t = min(t, sub1Dp[i-1][j]);
sub1Dp[i][j] = t + connectingCost;
}
}
return sub1Dp[n-1][m-1];
}
bool isSub2(vector<int> &r, vector<int> &b) {
return r.back() < b[0];
}
ll sub2(vector<int> &r, vector<int> &b) {
int n = r.size(), m = b.size();
ll rSum = 0;
for(int i=0; i<n; i++) {
rSum += r[n-1] - r[i];
}
ll bSum = 0;
for(int j=0; j<m; j++) {
bSum += b[j] - b[0];
}
ll connectingCost = (ll)(b[0] - r[n-1]) * max(n, m);
return rSum + bSum + connectingCost;
}
bool isSub3(vector<int> &r, vector<int> &b) {
int n = r.size(), m = b.size();
vector<int> v;
int i=0, j=0;
while(i < n && j < m) {
if(r[i] < b[j]) {
v.push_back(1);
i++;
}
else {
v.push_back(0);
j++;
}
}
for(; i<n; i++)
v.push_back(1);
for(; j<m; j++)
v.push_back(0);
int cnt = 1;
for(int i=1; i<v.size(); i++) {
if(v[i] == v[i-1])
cnt++;
else
cnt = 1;
if(cnt == 7) return false;
}
return true;
}
void makeVectors(vector<int> &pos, vector<int> &color, vector<int> &r, vector<int> &b) {
int n = r.size(), m = b.size();
int i=0, j=0;
while(i < n && j < m) {
if(r[i] < b[j]) {
pos.push_back(r[i]);
color.push_back(1);
i++;
}
else {
pos.push_back(b[j]);
color.push_back(0);
j++;
}
}
for(; i<n; i++) {
pos.push_back(r[i]);
color.push_back(1);
}
for(; j<m; j++) {
pos.push_back(b[j]);
color.push_back(0);
}
}
vector<int> subVector(vector<int> &v, int st, int ed) {
vector<int> res;
for(int i=st; i<=ed; i++) {
res.push_back(v[i]);
}
return res;
}
void printVector(vector<int> &v) {
printf("{");
for(int i=0; i<v.size(); i++) {
printf("%d,", v[i]);
}
printf("}\n");
}
ll sub3Dp[200010]; // minCost of v[0~i]
ll sub3(vector<int> &r, vector<int> &b) {
vector<int> pos, color;
makeVectors(pos, color, r, b);
//printVector(v); // OK
vector<int> leftRed, rightBlue;
int vSt = -1;
for(int vIdx=0; vIdx<pos.size(); vIdx++) {
sub3Dp[vIdx] = MAX;
rightBlue.push_back(pos[vIdx]);
if(color[vIdx] != color[vIdx+1]) {
vSt = vIdx + 1;
break;
}
}
int prevL = -1, prevR = -1;
/*
printf("(prevL, prevR) = (%d, %d)\n", prevL, prevR);
printf("leftRed: "); printVector(leftRed);
printf("rightBlue: "); printVector(rightBlue);*/
// OK
for(int vIdx=vSt; vIdx<pos.size(); vIdx++) {
sub3Dp[vIdx] = MAX;
if(color[vIdx] != color[vIdx-1]) {
prevL = prevR + 1;
prevR = vIdx-1;
leftRed = rightBlue;
rightBlue.clear();
/*
printf("vIdx = %d\n", vIdx);
printf("(prevL, prevR) = (%d, %d)\n", prevL, prevR);
printf("leftRed: "); printVector(leftRed);
printf("rightBlue: "); printVector(rightBlue);*/ // OK
}
rightBlue.push_back(pos[vIdx]);
//printf("(%d, %d), %d, rightBlue: ", v[vIdx].color, v[vIdx].pos, rightBlue.back());
//printVector(rightBlue);
for(int rSt=prevR; rSt>=prevL; rSt--) {
vector<int> leftRed = subVector(pos, rSt, prevR);
//printf("subRed: "); printVector(leftRed);
ll cost = sub2(leftRed, rightBlue);
if(sub3Dp[rSt] == MAX) {
if(rSt == prevL) {
sub3Dp[vIdx] = cost;
break;
}
else continue;
}
ll rest = sub3Dp[rSt];
if(sub3Dp[rSt-1] != MAX)
rest = min(rest, sub3Dp[rSt-1]);
/*if(vIdx == 6) {
printf("rSt=%d: cost = %lld rest = %lld\n", rSt, cost, rest);
}*/
sub3Dp[vIdx] = min(sub3Dp[vIdx], cost + rest);
}
//printf("sub3Dp[%d] = %lld\n", vIdx, sub3Dp[vIdx]);
}
return sub3Dp[pos.size()-1];
}
ll min_total_length(vector<int> r, vector<int> b) {
int n = r.size(), m = b.size();
if(isSub1(n, m)) {
return sub1(r, b);
}
else if(isSub2(r, b)) {
return sub2(r, b);
}
else if(isSub3(r, b)) {
return sub3(r, b);
}
else return -1;
}
