分数: 600 点
问题陈述
有长度-N 序列 A=(A_0,A_1,\ldots,A_{N-1}) 和 B=(B_0,B_1,\ldots,B_{N-1}).
Takahashi 可能会执行以下操作 A 任意次数(可能为零):
- 对序列应用左循环移位 A。 换句话说,替换 A 与 A' 定义为 A'_i=A_{(i+1)\% N},其中 x\% N 表示当 x 除以 N.
高桥的目标是最大化 \displaystyle\sum_{i=0}^{N-1} (A_i|B_i),其中 x|y 表示按位逻辑和(按位或) x 和 y.
找到可能的最大值 \displaystyle\sum_{i=0}^{N-1} (A_i|B_i).
什么是按位逻辑和(按位或)?
的 逻辑和 (或 OR 运算)是对两个一位整数的运算(0 or 1)由下表定义。的 按位逻辑和(按位或) 是逐位应用逻辑和的操作。
| x | y | x|y |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
逻辑和产生 1 如果至少一位 x 和 y is 1。 相反,它产生 0 仅当两者都是 0.
示例
0110 | 0101 = 0111
约束
- 2 \leq N \leq 5\times 10^5
- 0\leq A_i,B_i \leq 31
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N
A_0 A_1 \ldots A_{N-1}
B_0 B_1 \ldots B_{N-1}
输出
打印最大可能值 \displaystyle\sum_{i=0}^{N-1} (A_i|B_i).
示例输入 1
3 0 1 3 0 2 3
示例输出 1
8
如果高桥不执行该操作, A 仍然 (0,1,3),我们有 \displaystyle\sum_{i=0}^{N-1} (A_i|B_i)=(0|0)+(1|2)+(3|3)=0+3+3=6;
如果他执行一次操作,则 A=(1,3,0),我们有 \displaystyle\sum_{i=0}^{N-1} (A_i|B_i)=(1|0)+(3|2)+(0|3)=1+3+3=7;和
如果他执行该操作两次,则 A=(3,0,1),我们有 \displaystyle\sum_{i=0}^{N-1} (A_i|B_i)=(3|0)+(0|2)+(1|3)=3+2+3=8.
如果他执行该操作三次或以上, A 成为上述序列之一,因此最大可能 \displaystyle\sum_{i=0}^{N-1} (A_i|B_i) is 8,应打印。
示例输入 2
5 1 6 1 4 3 0 6 4 0 1
示例输出 2
23
如果他执行三次操作,该值将最大化,使得 A=(4,3,1,6,1),
其中 \displaystyle\sum_{i=0}^{N-1} (A_i|B_i)=(4|0)+(3|6)+(1|4)+(6|0)+(1|1)=4+7+5+6+1=23.