背景
题目来源:【HT-126-Div.3】核桃 CSP-J 组模拟赛
题目描述
小 R 在玩一个合成游戏。有 n 个元素排成一排,第 i 个元素的类型为 ai∈[0,m−1]。
小 R 可以无限次执行下面的合成操作:
- 选择相邻的两个元素,设它们的类型为 x 和 y,将它们合并成一个元素,新元素的类型为 x⊕y。
游戏结束后,每个剩余元素若类型为 t,则会提供 Bt 的分数。小 R 想知道,通过进行合成操作,他最多能获得的总分。
对于所有 0≤i<m,Bi 将给出;对于所有 i≥m,Bi=0。
输入格式
第一行,两个整数 n,m,分别表示元素个数和值域大小。
第二行, n 个整数 a1,a2,…,an。
第三行, m 个整数 B0,B1,…,Bm−1。
输出格式
一个整数,表示最大总分。
3 8
1 2 3
0 10 20 30 0 0 0 0
60
提示
【数据范围】
对于 24% 的数据,1≤n,m≤20。
对于 48% 的数据,1≤n≤2000。
对于 100% 的数据,1≤n≤5×105,2≤m≤256,m 是 2 的正整数次幂,0≤ai<m,0≤Bt≤104。