問題一覧 >
通常問題
No.2071 Shift and OR
レベル :
/ 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ :
/
解いたユーザー数 129
作問者 :
taiga0629kyopro
/ テスター :
遭難者
問題文最終更新日: 2022-09-17 00:07:54
問題文
長さ N の整数列 A が与えられます。また整数 x に対して関数 shift(x)
を次のように定めます。
shift(x)=⌊2x⌋+215×(x mod 2)
あなたは次の操作を何度でも行うことができます。(1 回も行わなくても良い。)
- 1≤i≤N を満たす整数 i を1つ選び、Ai を shift(Ai) に置き換える。
操作後の A1 OR A2 OR…OR AN としてあり得る値のうち最大値を求めてください。
ただし、OR はビットごとの論理和を表します。
▶︎⌊2x⌋ とは(クリックで開く)
⌊2x⌋ で x を 2 で割った時の商を表します。
▶︎x mod 2 とは(クリックで開く)
x mod 2 で x を 2 で割った余りを表します。
入力
N
A1 A2 … AN
1≤N≤2×105
1≤Ai<216
入力は全て整数
出力
操作を行った後の A1 OR A2 OR…OR AN
の最大値を出力してください。
サンプル
サンプル1
入力
2
1 2
出力
49152
次のように操作を行います。
- i=1 とする。A=(32768,2) となる。
- i=2 とする。A=(32768,1) となる。
- i=2 とする。A=(32768,32768) となる。
- i=2 とする。A=(32768,16384) となる。
A1 OR A2=49152 となり、これが最大です。
サンプル2
入力
3
6 2 9
出力
63488
サンプル3
入力
5
3 1 4 1 5
出力
65024
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。