33OJ
登录 注册

#P17754. 「RSOI-3C」合成游戏 / game

    ID: 20425 远端评测题 1000ms 512MiB 尝试: 0 已通过: 0 显示难度普及 上传者: 标签>动态规划 DPO2优化位运算2026

「RSOI-3C」合成游戏 / game

背景

题目来源:【HT-126-Div.3】核桃 CSP-J 组模拟赛

题目描述

小 R 在玩一个合成游戏。有 nn 个元素排成一排,第 ii 个元素的类型为 ai∈[0,m−1]a_i \in [0, m-1]。

小 R 可以无限次执行下面的合成操作:

  • 选择相邻的两个元素,设它们的类型为 xx 和 yy,将它们合并成一个元素,新元素的类型为 x⊕yx \oplus y。

游戏结束后,每个剩余元素若类型为 tt,则会提供 BtB_t 的分数。小 R 想知道,通过进行合成操作,他最多能获得的总分。

对于所有 0≤i<m0 \le i < m,BiB_i 将给出;对于所有 i≥mi \ge m,Bi=0B_i=0。

输入格式

第一行,两个整数 n,mn, m,分别表示元素个数和值域大小。

第二行, nn 个整数 a1,a2,…,ana_1, a_2, \dots, a_n。

第三行, mm 个整数 B0,B1,…,Bm−1B_0, B_1, \dots, B_{m-1}。

输出格式

一个整数,表示最大总分。

3 8
1 2 3
0 10 20 30 0 0 0 0
60

提示

【数据范围】

对于 24%24\% 的数据,1≤n,m≤201\le n,m \le 20。

对于 48%48\% 的数据,1≤n≤20001\le n \le 2000。

对于 100%100\% 的数据,1≤n≤5×1051 \le n \le 5 \times 10^5,2≤m≤2562 \le m \le 256,mm 是 22 的正整数次幂,0≤ai<m0 \le a_i < m,0≤Bt≤1040 \le B_t \le 10^4。