問題一覧 > 通常問題

No.1246 ANDORゲーム(max)

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 42
作問者 : 👑 tute7627 / テスター : tempura_pp
8 ProblemId : 4320 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2020-10-03 01:33:11

問題文

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

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

入力

N T
A1 A2 … AN

  • 入力は全て整数である。
  • 1≤N≤105
  • 0≤T≤109
  • 0≤Ai≤109

出力

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

サンプル

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

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

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

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

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

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