問題一覧 > 通常問題

No.1246 ANDORゲーム(max)

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 34
作問者 : tute7627tute7627 / テスター : tempura_pptempura_pp
6 ProblemId : 4320 / 出題時の順位表
問題文最終更新日: 2020-10-03 01:33:11

問題文

あなたは以下のようなゲームを行うことにしました。

  • ゲームの開始時にあなたは非負整数 $T$ を持っており、スコアは $0$ である。
  • 長さ $N$ の数列 $A$ を用いて以下の操作を $N$ 回繰り返す。
    • $i$ 回目の操作では、現在持っている整数を $X$ として、$X$ を以下のどちらかに変化させる。
      • $X$ と $A_i$ の bitwise and
      • $X$ と $A_i$ の bitwise or
    • 各操作後に、スコアが $|(変化後のX) - (変化前のX)|$ 増加する。
$N$ 回の操作後のスコアの最大値を求めてください。

入力

$N\ T$
$A_1\ A_2\ \dots\ A_N$

  • 入力は全て整数である。
  • $1 \le N \le 10^5$
  • $0 \le T \le 10^9$
  • $0 \le A_i \le 10^9$

出力

$N$ 回の操作後のスコアの最大値を出力してください。最後に改行してください。

サンプル

サンプル1
入力
4 2
0 1 0 2
出力
6

例えば、bitwise or, bitwise or, bitwise and, bitwise or の順で選択すれば良いです。
$1$ 回目の操作では、持っている整数は $2 \to 2$ となり、スコアは $0$ のままです。
$2$ 回目の操作では、持っている整数は $2 \to 3$ となり、スコアは $1$ になります。
$3$ 回目の操作では、持っている整数は $3 \to 0$ となり、スコアは $4$ になります。
$4$ 回目の操作では、持っている整数は $0 \to 2$ となり、スコアは $6$ になります。

サンプル2
入力
3 1
1 1 1
出力
0

どのような選択をしても持っている整数は変わりません。

サンプル3
入力
5 6
1 5 3 2 1
出力
20

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。