まず、スコアのうち \((A_i\mathbin{\mathrm{AND}}A_j)\mathbin{\mathrm{XOR}}(A_i\mathbin{\mathrm{OR}}A_j)\) の部分を簡単に表すことを考えます。いずれの演算もビットごとに独立なので、\((0,0),(0,1),(1,0),(1,1)\) の場合を計算します。

• \((0\mathbin{\mathrm{AND}}0)\mathbin{\mathrm{XOR}}(0\mathbin{\mathrm{OR}}0) = 0\mathbin{\mathrm{XOR}}0=0\)
• \((1\mathbin{\mathrm{AND}}0)\mathbin{\mathrm{XOR}}(1\mathbin{\mathrm{OR}}0) = 0\mathbin{\mathrm{XOR}}1=1\)
• \((0\mathbin{\mathrm{AND}}1)\mathbin{\mathrm{XOR}}(0\mathbin{\mathrm{OR}}1) = 0\mathbin{\mathrm{XOR}}1=1\)
• \((1\mathbin{\mathrm{AND}}1)\mathbin{\mathrm{XOR}}(1\mathbin{\mathrm{OR}}1) = 1\mathbin{\mathrm{XOR}}1=0\)

すると、スコアは \(A_i+A_j-(A_i\mathbin{\mathrm{XOR}}A_j)\) と表せることが分かります。ここで、\(2\) 進数における足し算の繰り上がりを考えると、任意の非負整数 \(a,b\) について \(a+b=2\times(a\mathbin{\mathrm{AND}}b)+(a\mathbin{\mathrm{XOR}}b)\) が成立するので、結局スコアは \(2\times(A_i\mathbin{\mathrm{AND}}A_j)\) と表せます。

\(A_i\mathbin{\mathrm{AND}}A_j\) の最大値は上位の桁から貪欲に決めていけば良いので、計算量 \(O(N\log\max A)\) で解くことができます。オーバーフローに注意しましょう。

実装例 (C++ 102 ms)