第5回 ドワンゴからの挑戦状 予選 B - Sum AND Subarrays

問題
提出コード

解法

たかだか1000個の数字しかないので、まずはあり得る部分列の和をすべて書き出します。
その後、一番大きい数字を2進数に直したときの、一番左側のビットから順番に、使用できるかどうかを判定していきます。
左側から順番に使用すると決めていけば、それより大きい数字を作ることはできなくなります(1000は、0111よりも大きいので)。
ということで、降順にソートします。
今見るビットをとします。 そこから個大きい順に見ていき、すべて以上であれば、このビットを使用することができるので、答えに加算します。
そうでなかったら、このビットを使用することはできません。
この後は、を使用するかどうかで操作が変わります。

• 使用する場合
  現在以上の数字から、を使用するかどうかを決めます。
  以上の数字すべてについて、を引いていき、引いた区間のみに対して降順にソートをし直します。あとは、を使用するかどうかを上と同じ手順で調べれば大丈夫です。

• 使用しない場合
  今見た全ての区間について、を使用するかどうかを決めます。
  まずは、以上の数字は、を引き算して、そのビットを消します。あとは、全ての区間を降順でソートしなおしていき、を使用するかどうかを上と同じ手順で調べれば大丈夫です。

これを繰り返してでてきた数字が最終的な答えになります。