View this problem on POJ: 1990 MooFest.
Here is my resolution:
First, sort cows by v value.
Then, for each cow in ascend order,
calculate DS : the sum of the differences of distances between this cow and each of the dealted cows. The answer is \(\sum_i{DS_i v_i}\)
How to calculate DS? Use TreeStructure Array.
TreeStructure Array may be used to
 store the number of cows that has a smaller \(x\) value as \(N_i\) for the \(i\)th cow.
 store the sum of \(x\) values which is smaller than the \(x\) value of the current cow as \(S_i\) for the \(i\)th cow.
The sum of all \(x\) values when dealing the \(i\)th cow can be calculated, which we denote as \(T_i\).
Then \(DS_i = (x_i N_i  S_i) + [(T_i  S_i)  (i  1  N_i) x_i]\)
The sort costs \(O(n log(n))\) (if you use quick sort), or \(O(n)\) (if you use radix sort).
For each cow, we need \(O(log(n))\) to calculate the DS(i), this is decided by the algorithm of TreeStructure Array.
So, the total complexity of this algorithm is \(O(n log(n))\).^{1}
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 


For this problem, the answer may exceed the scope of 32bit integer , so you may use int64 or long long in C++ language, or BigInteger in Java.↩