# CFR 439 D. Devu and his Brother ( Ternary Search )

Problem - D - Codeforces

O( log( max{ A } ) * ( N + M ) ) / O( N + M )

```int N, M;
vi A;
vi B;

void init(){
cin >> N >> M;
A = vi( N );
for( int i = 0; i < N; ++i ){
cin >> A[ i ];
}
B = vi( M );
for( int i = 0; i < M; ++i ){
cin >> B[ i ];
}
}

ll get_cost( int apex ){
ll res = 0;
for( int i = 0; i < N; ++i ){
if( A[ i ] < apex ){
res += apex - A[ i ];
}
}
for( int i = 0; i < M; ++i ){
if( B[ i ] > apex ){
res += B[ i ] - apex;
}
}
return res;
}

void preprocess(){
int lb, rb;
for( lb = 1, rb = ( ll ) 1e10; rb - lb > 10; ){
int x = ( 2LL * lb + rb ) / 3;
int y = ( 2LL * rb + lb ) / 3;
ll cl = get_cost( lb );
ll cx = get_cost( x );
ll cy = get_cost( y );
ll cr = get_cost( rb );
if( cl <= cx and cx <= cy and cy <= cr ){
rb = x;
} else if( cl >= cx and cx <= cy and cy <= cr ){
rb = y;
} else if( cl >= cx and cx >= cy and cy <= cr ){
lb = x;
} else if( cl >= cx and cx >= cy and cy >= cr ){
lb = y;
} else{
assert( false );
}
}
ll ans = 1LL << 62;
for( int i = lb; i <= rb; ++i ){
upmin( ans, get_cost( i ) );
}
cout << ans << endl;
}
```