Suppose we have determined the positions of dogs, we could know the coefficients (means \(|x-y|\)) of each position. According to the Rearrangement Inequality, we can calculate the contribution of dogs and cats separately in \(O(n)\).

By using Simulated Annealing and a few dirty tricks, we can solve the problem easily in 1900ms .

In the SA, we have a permutation \(p\) of \(1\sim (n+m)\), which the first \(n\) elements represent the positions of dogs, and the rest of them represent cats. Every time we randomly choose two indices \(i\in [1,n],j\in [n+1,n+m]\) then swap \(p_i,p_j\). You can see more details in code from my friend .