← 返回题目列表

AtCoder · awc0082_b

B. 最大化灯序列的分区分数

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

分数: 333 分

问题陈述

高桥有一个设备 N 灯排成一排。每个灯要么亮(1)或关闭(0).

将灯从左到右表示为 b_1, b_2, \ldots, b_N,设备的状态用整数表示

X = \sum_{i=1}^{N} b_i \cdot 2^{i-1}

也就是说, i从左边数第一个灯, b_i,对应于 i- 二进制表示中从底部算起的第 X (最左边的灯是最低有效位)。

在高桥的设备上重复执行以下操作。该操作最多执行 K 次,但可能中途停止。

一次操作: 检查当前序列最左边的灯。


- 如果它打开(1),什么都不做并且 终止所有操作.

- 如果它关闭(0),从序列中删除该灯并在(1)灯向右端(序列的长度保持不变) N)。如果操作次数还没有达到 K,再次执行该操作。

换句话说,“只要最左边的灯关闭,将其移除并在右端添加一个打开的灯”,执行到 K 次。当确认最左边的灯亮时,或者当 K 操作已执行。

在此过程之后,青木带来了 M 灯序列。每个灯序列也有长度 N,以及状态 j第灯序列由整数表示 Y_j,使用与高桥设备相同的位对应关系。

高桥选择单一共同分割位置 p (1 \le p \le N - 1)对于所有人 M + 1 灯序列 — 他自己处理的灯序列和青木的 M 灯序列。每个灯序列分为左 p 灯和右 N - p 灯。

对于每个灯序列,让 左部分 从左到右是 c_1, c_2, \ldots, c_p,其整数值定义为

\sum_{i=1}^{p} c_i \cdot 2^{i-1}

让 A 是所有左边部分的整数值的总和 M+1 灯序列。

类似地,对于每个灯序列,让 右部分 从左到右是 d_1, d_2, \ldots, d_{N-p},其整数值定义为

\sum_{i=1}^{N-p} d_i \cdot 2^{i-1}

(请注意, 2 重新启动 2^0 在右侧部分内。)让 B 是所有右侧部分的整数值之和 M+1 灯序列。

高桥选择分割位置 p 最大化 A + B。找到最大值 A + B.

约束

  • 2 \leq N \leq 46
  • 0 \leq K \leq 10^9
  • 0 \leq M \leq 2 \times 10^5
  • 0 \leq X < 2^N
  • 0 \leq Y_j < 2^N (1 \leq j \leq M)
  • 所有输入均为整数
  • 在这些约束下,答案适合有符号 64 位整数

输入

N K M X
Y_1 Y_2 \ldots Y_M

第一行包含灯序列的长度 N,最大操作数 K,附加灯序列的数量 M,以及高桥设备的初始状态 X,用空格分隔。

当 M \geq 1,第二行包含 M 整数 Y_1, Y_2, \ldots, Y_M 表示附加灯序列的状态,以空格分隔。

当 M = 0,第二行不存在。

输出

输出最大值 A + B 一行。


示例输入 1

5 2 2 4
3 16

示例输出 1

23

示例输入 2

4 0 1 9
6

示例输出 2

8

示例输入 3

12 7 6 1384
0 4095 2730 1365 2048 1234

示例输出 3

7616

示例输入 4

46 1000000000 10 35184372088832
0 1 70368744177663 70368744177662 35184372088831 35184372088832 1234567890123 45678901234567 60000000000000 42

示例输出 4

194194222917695

示例输入 5

2 1000000000 0 0

示例输出 5

2