CF413C.Jeopardy!

普及/提高-

通过率:0%

时间限制:1.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

'Jeopardy!' is an intellectual game where players answer questions and earn points. Company Q conducts a simplified 'Jeopardy!' tournament among the best IT companies. By a lucky coincidence, the old rivals made it to the finals: company R1 and company R2.

The finals will have n questions, m of them are auction questions and n - m of them are regular questions. Each question has a price. The price of the i-th question is a__i points. During the game the players chose the questions. At that, if the question is an auction, then the player who chose it can change the price if the number of his current points is strictly larger than the price of the question. The new price of the question cannot be less than the original price and cannot be greater than the current number of points of the player who chose the question. The correct answer brings the player the points equal to the price of the question. The wrong answer to the question reduces the number of the player's points by the value of the question price.

The game will go as follows. First, the R2 company selects a question, then the questions are chosen by the one who answered the previous question correctly. If no one answered the question, then the person who chose last chooses again.

All R2 employees support their team. They want to calculate what maximum possible number of points the R2 team can get if luck is on their side during the whole game (they will always be the first to correctly answer questions). Perhaps you are not going to be surprised, but this problem was again entrusted for you to solve.

《危险边缘!》(Jeopardy!)是一档智力问答类节目,参赛者通过回答问题来赢得积分。Q 公司面向顶尖 IT 企业举办了一场简化的《危险边缘!》锦标赛。巧合的是,老对手 R1 公司与 R2 公司双双闯入决赛。

决赛共包含 $ n $ 道题目,其中 $ m $ 道为“拍卖题”(auction questions),其余 $ n - m $ 道为“普通题”(regular questions)。每道题目均有对应分值:第 $ i $ 道题的原始分值为 $ a_i $ 分。比赛过程中,选手轮流选择题目。若所选题目为拍卖题,则选择该题的选手可在其当前积分严格大于该题原始分值时,自主调整该题分值;调整后的分值不得低于原始分值,且不得超过该选手当前拥有的积分。答对题目后,选手获得的积分为该题最终分值;答错则从该选手当前积分中扣除该题最终分值。

比赛流程如下:首先由 R2 公司选择一道题目;此后,由上一题答对者继续选择下一题;若上一题无人答对,则仍由上一轮选择题目的选手再次选题。

R2 公司全体员工全力支持本队。他们希望计算:在整场游戏全程运气极佳(即 R2 总是第一个正确作答所有题目的前提下),R2 公司所能获得的最高可能积分。或许你并不感到意外——这一问题再次交由你来解决。

输入格式

The first line contains two space-separated integers n and m (1 ≤ n, m ≤ 100; m ≤ min(n, 30)) — the total number of questions and the number of auction questions, correspondingly. The second line contains n space-separated integers _a_1, _a_2, ..., a__n (1 ≤ a__i ≤ 107) — the prices of the questions. The third line contains m distinct integers b__i (1 ≤ b__i ≤ n) — the numbers of auction questions. Assume that the questions are numbered from 1 to n.

第一行包含两个以空格分隔的整数 nn 和 mm(1≤n,m≤1001 \leq n, m \leq 100;m≤min⁡(n,30)m \leq \min(n, 30)),分别表示问题总数和拍卖类问题的数量。
第二行包含 nn 个以空格分隔的整数 a1,a2,…,ana_1, a_2, \dots, a_n(1≤ai≤1071 \leq a_i \leq 10^7),表示各问题的价格。
第三行包含 mm 个互不相同的整数 bib_i(1≤bi≤n1 \leq b_i \leq n),表示拍卖类问题的编号。
假设问题编号从 11 到 nn。

输出格式

In the single line, print the answer to the problem — the maximum points the R2 company can get if it plays optimally well. It is guaranteed that the answer fits into the integer 64-bit signed type.

在单行中输出该问题的答案——即 R2 公司在最优策略下所能获得的最大得分。保证答案在 64 位有符号整数范围内。

输入输出样例

  • 输入#1

    4 1
    1 3 7 5
    3

    输出#1

    18
  • 输入#2

    3 2
    10 3 8
    2 3

    输出#2

    40
  • 输入#3

    2 2
    100 200
    1 2

    输出#3

    400

输入解题思路,AI测评打分。不知道怎么写?

首页