1309:Singing and Dancing

时间限制: 2 S | 内存限制: 65536 KB
Accept: 0 | Submit: 0
[提交] [状态] [讨论版]
描述

在一场歌舞会上有 n 个表演者,他们每个人都有一个唱歌能力 si 和跳舞能力 di,我们先假设有 x (0 <= x <= n) 个人唱歌,n - x 个人跳舞。其中,这 x 个歌手分为 a (0 <= a <= x) 个主歌手和 x - a 个副歌手,n - x 个舞者分为 b (0 <= b <= n - x) 个主舞者和 n - x - b 个副舞者。接下来我们定义:

歌舞会的精彩度 = 唱歌精彩度 * 跳舞精彩度。

唱歌精彩度 = a 个主歌手的唱歌能力之按位异或 + (x - a) 个副歌手的唱歌能力之按位或。

跳舞精彩度 = b 个主舞者的跳舞能力之按位异或 + (n - x - b) 个副舞者的跳舞能力之按位与。

如何进行角色分配才能使这场歌舞会尽可能精彩?

输入

第一行是一个正整数 n 代表表演者的数量。(1 <= n <= 10)

第二行是 n 个正整数 si,第 i 个数字代表第 i 个表演者的唱歌能力。(1 <= si <= 1e8)

第三行是 n 个正整数 di,第 i 个数字代表第 i 个表演者的跳舞能力。(1 <= di <= 1e8)

输出

这场歌舞会可以达到的最大精彩度,然后换行。

样例输入

2

3 4

5 6

样例输出
20
HINT

Q:如何理解 “唱歌精彩度” 中的 “a 个主歌手的唱歌能力之按位异或”?

A:假设这 a 个主歌手的编号分别为 1 ~ a,那么这 “a 个主歌手的唱歌能力之按位异或” = s1 ^ s2 ^ … ^ sa。

Q:当 a 取值为 x 时不就相当于全部的歌手都去当主歌手了吗,那此时 “(x - a) 个副歌手的唱歌能力之按位或” 该如何计算?

A:若主歌手、副歌手、主舞者、副舞者的其中几项人数为 0 时,其对应的能力值也为 0。

来源
Hello winter vacation Round#4