← 返回题目列表

AtCoder · abc291_g

G. 或总和

中文机器翻译题面 查看原题

分数: 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.