[Codeforces] D. Devu and his Brother

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : D. Devu and his Brother
                    Codeforces Round #251 (Div. 2)
Source            : Codeforces
Category          : Search
Algorithm         : Ternary Search
Verdict           : Accepted 

#include <bits/stdc++.h>  
   
using namespace std;  
   
static const int MAXN = 1e5 + 5;  
   
int n, m;  
long long A[MAXN], B[MAXN];  
long long SA[MAXN], SB[MAXN];  
   
long long f(long long num)  
{  
    int nn = lower_bound(A+1, A+n+1, num) - A;  
    long long changeA = num*(nn-1) - SA[nn-1];  
    int mm = lower_bound(B+1, B+m+1, num+1) - B;  
    long long changeB = 0;  
    if (mm <= m) changeB = SB[m] - SB[mm-1] - num*(m-mm+1);  
    return changeA + changeB;  
}  
   
long long ternary()  
{  
    long long low = 1;  
    long long high = 1e9;  
    while (true)  
    {  
        if (high - low < 3)  
        {  
            long long f1 = f(low);  
            long long f2 = f(low+1);  
            long long f3 = f(high);  
            return min(f1, min(f2, f3));  
        }  
        long long midA = low + (high - low)/3;  
        long long midB = high - (high - low)/3;  
        if (f(midA) <= f(midB)) high = midB;  
        else low = midA;  
    }  
}  
   
int main()  
{  
    cin >> n >> m;  
    for (int i = 1; i <= n; i++) cin >> A[i];  
    sort(A+1, A+n+1);  
    for (int i = 1; i <= n; i++) SA[i] = SA[i-1] + A[i];  
    for (int i = 1; i <= m; i++) cin >> B[i];  
    sort(B+1, B+m+1);  
    for (int i = 1; i <= m; i++) SB[i] = SB[i-1] + B[i];  
    cout << ternary();  
}