← 返回题目列表

AtCoder · abc014_2

B. 总价

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

問題文

 您正在购物并从商品列表中选择一些商品。现在我们正在尝试总结产品的价格。

 顺便说一句,如果某个集合的任何子集是 2 有一种使用基数来表达它的方法,可以在 for 循环中枚举所有子集(组合)时使用。 有

  • n 产品,产品 假设我们有0,商品1,..,商品n-1 。下标是 请注意,它以0开头。
  • 代表子集 10 十进制整数 X 及其 2 進 n 数字表示b_{n-1}b_{n-2}...b_1b_0。b_0 是最低有效位 b_{n-1} 是最高有效位。第一 请注意,此表达式允许0 。

这个整数 X 的 2 使用十六进制表示定义某个子集如下。

  • b_0=1 那么该套装就是一个产品 包含0 , 不包括b_0=0 那么该套装就是一个产品 包含 0 。
  • b_1=1 那么该套装就是一个产品 包含1 , 不包括b_1=0 那么该套装就是一个产品 包含 1 。
  • ...
  • b_{n-1}=1 那么该套装就是一个产品 包含 n-1 , 不包括b_{n-1}=0 那么该套装就是一个产品 包含 n-1 。

例如, 当n=4,X=5 时, b=0101 子集是 \{商品0,商品2\} 。 简单地说,X的 2 在基本表示中, 如果设置了第k(0 ≦ k ≦ n-1) 位 这意味着它包含第 k 项。在许多编程语言中可以很容易地确定某个位是否被设置,因此请自行检查。

 您的工作是表示产品数量、每种产品的价格以及子集 给定 10 進整数 X ,任务是对子集中包含的产品的价格进行求和。

 *虽然与这个问题没有直接关系,但通过如上表示子集,大小 集合 n 的所有子集(包括空集) 它可以表示为0 ~ 2^n-1 连续整数,因此建议在执行完整枚举时应用它。


入力

输入是按以下格式从标准输入给出的。

n X
a_0 a_1 a_2 ... a_{n-1}
  • 1 该行产品数量 n (1 ≦ n ≦ 20) 代表产品的子集 10 進整数 X (0 ≦ X ≦ 2^{n}-1) 用空格分隔。 在
  • 2 系列中,产品 0 ~ n-1 产品价格 a_0,a_1,...,a_{n-1}(0 ≦ a_0,a_1,...,a_{n-1} ≦ 1,000) 按顺序给出,用空格分隔。

出力

  • 子集中包含的产品价格总和为 在 1 行输出。在输出末尾插入换行符。

入力例1

4 5
1 10 100 1000

出力例1

101

n 和 X 是问题文本中的解释中使用的值。子集是\{商品0,商品2\},所以1+100=101变为。


入力例2

20 1048575
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

出力例2

210

X 的 2 十六进制表示为11111111111111111111(20的1已排列),因此该子集包括所有产品。


入力例3

4 0
1000 1000 1000 1000

出力例3

0

子集可以是空集。