これを効率的に解決する方法は？

Question

Iは、2つの配列を有する：

pos[n]

1. score[n]が、ここで、n < = 10^5。 POS [i]は、[i]は< = 10^4

が定義スコア：

f(i,j) = abs(pos[i]-pos[j])*max(score[i],score[j]) 

は、私はすべてのi,j秒間f(i,j)の合計を見つける必要があります。
私はO(n^2)で解決できるアルゴリズムを持っていますが、私は最適化したいです。
私は多くの時間を費やしましたが、できませんでした。

何か助けていただければ幸いです。 最悪の場合のコード http://ideone.com/q4qSNh

Answer 1

先ほど同様の質問があります。 hereを参照してください。

@Gribouillisは、O(nlogn)の複雑さを持つ素敵なアルゴリズムを提供しました。このアルゴリズムは、ソートとバランスのとれたバイナリ検索ツリーを使用しています。完全回答はhereをご覧ください

実装は練習問題として残っています。