No.1246 ANDORゲーム(max)
タグ : / 解いたユーザー数 42
作問者 : 👑
tute7627
/ テスター :
tempura_pp
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Show the original
Problem Statement
You have decided to play the following game.
- At the start of the game, you hold a non-negative integer $T$, and your score is $0$.
- Using a sequence $A$ of length $N$, repeat the following operation $N$ times.
- In the $i$-th operation, let $X$ be the integer you currently hold, and change $X$ to one of the following.
- The bitwise and of $X$ and $A_i$
- The bitwise or of $X$ and $A_i$
- After each operation, the score increases by $|(変化後のX) - (変化前のX)|$, where 変化後のX and 変化前のX denote the value of X after the change and before the change, respectively.
Input
$N\ T$ $A_1\ A_2\ \dots\ A_N$
- All input values are integers.
- $1 \le N \le 10^5$
- $0 \le T \le 10^9$
- $0 \le A_i \le 10^9$
Output
Output the maximum possible score after the $N$ operations. Print a newline at the end.
Sample
Sample 1
Input
4 2 0 1 0 2
Output
6
For example, you can choose bitwise or, bitwise or, bitwise and, bitwise or, in this order.
In operation $1$, the integer you hold changes as $2 \to 2$, and the score remains $0$.
In operation $2$, the integer you hold changes as $2 \to 3$, and the score becomes $1$.
In operation $3$, the integer you hold changes as $3 \to 0$, and the score becomes $4$.
In operation $4$, the integer you hold changes as $0 \to 2$, and the score becomes $6$.
Sample 2
Input
3 1 1 1 1
Output
0
No matter what you choose, the integer you hold does not change.
Sample 3
Input
5 6 1 5 3 2 1
Output
20
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。