// moreflags=grader.cpp
//
// 13
#include "wiring.h"
#include<vector>
#if not LOCAL
#define NDEBUG
#endif
#include<cassert>
#include<map>
#include<algorithm>
long long min_total_length(std::vector<int> red, std::vector<int> blue) {
auto const nearest=[&](std::vector<int> const& first, std::vector<int> const& sec){
auto iterator=sec.begin();
std::vector<int> result; result.reserve(first.size());
for(auto it: first){
while(iterator!=sec.end() and *iterator<it) ++iterator;
assert(iterator==std::lower_bound(begin(sec), end(sec), it));
result.push_back(
iterator==sec.begin() or (iterator!=sec.end() and *iterator-it<it-iterator[-1]) ?
int(iterator-sec.begin()): int(iterator-sec.begin()-1)
);
}
return result;
};
auto const redNear=nearest(red, blue);
auto const blueNear=nearest(blue, red);
std::vector<std::map<int, int64_t>> f(red.size());
auto const optimize=[&](int i, int j, int64_t oldValue){
int64_t const value=oldValue+std::abs(red[i]-blue[j]);
auto [iterator, inserted]=f[i].insert({j, value});
if(not inserted) iterator->second=std::min(iterator->second, value);
};
optimize(0, 0, 0);
for(int i=0; i<(int)red.size(); ++i){
if(i!=0) f[i-1].clear();
for(auto [j, value]: f[i]){
bool const imaximum=i==(int)red.size()-1, jmaximum=j==(int)blue.size()-1;
if(imaximum and jmaximum)
return value;
if(not imaximum){
if(not jmaximum)
optimize(i+1, j+1, value);
if(redNear[i]==j and redNear[i+1]==j)
optimize(i+1, j, value);
}
if(not jmaximum)
if(blueNear[j]==i and blueNear[j+1]==i)
optimize(i, j+1, value); // map doesn't invalidate iterators
}
}
assert(false); __builtin_unreachable();
}
