codeforces 415 div2 C

Problem - C - Codeforces

入力列をソートしておいても関係ないため、あらかじめソートされた入力列について考える。
また、関数F(a)は頂点の集合の最大値・最小値にのみ依存する。

例として数列8, 6, 5, 3, 2, 1が入力されたときを考える。
このときの答えは

(8-6)*1 + (8-5)*2 + (8-3)*4 + (8-2)*8 + (8-1)*16
        + (6-5)*2 + (6-3)*4 + (6-2)*8 + (6-1)*16
                  + (5-3)*4 + (5-2)*8 + (5-1)*16
                            + (3-2)*8 + (3-1)*16
                                      + (2-1)*16
= 8*(2^5-1) + 6*(2^4-1) + 5*(2^3-1) + 3*(2^2-1) + 2*(2^1-1)
  -{1*(2^5-1) + 2*(2^4-1) + 3*(2^3-1) + 5*(2^2-1) + 6*(2^1-1) 

となる。最大値と最小値を固定したとき、その集合の個数は 1 + 2 + 4 + … + 2^(n-1) = (2^n)-1で求められる。よって、それぞれの数が最大値として使われる回数と最小値として使われる回数をO(1)で求めることができ、合計でO(n)で答えを求められる。オーバーフローに注意。