#C. 卡牌策略(card)

    传统题 1000ms 256MiB

卡牌策略(card)

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

你会贪心吗?答案是显而易见的,你当然会,只是贪心是多变的,贪心是难以证明的,直接看到的做法并不保证其是正解,还是需要多加斟酌,确定正解。一瞬的灵感和真实,不可同论,是两回事情。

Description

就来WDG和你来一场游戏吧,WDG和你进行,你先手。

场上平摊有nn张牌,每张牌都有一个对应的分数AiA_i,取得到这张牌,会让你的分数+Ai+A_i,你的初始分数为00,在游戏结束时你要让自己取得的分数尽可能高

在每回合中,你可以选择:

  • 取走场上的任意一张牌,然后WDG取走任意一张牌
  • 取走场上的任意xx张牌,然后WDG取走任意yy张牌

双方拿完牌后,这回合结束。

在游戏的过程中,可能会出现没牌可取的情况,一旦双方出现需要取的牌的和的数量大于场上剩余牌的数量的情况,则游戏立刻结束。

WDG对于胜负其实无所谓,他不需要在比赛中取得高分,他只希望让你的分数尽可能低,他知道什么用方法可以让你的分数尽可能低。

所以,你最多可以拿到多少分呢?

Format

Input

第一行输入三个正整数n,x,yn,x,y

第二行输入nn整数,第ii个数为AiA_i

Output

你最多可以取得的分数

Samples

8 2 3
1000 100 2 3 7 10 -8 - 3
1102

第一轮:你拿走1000,1001000,100,然后WDG拿走10,7,310,7,3

第二轮:你拿走22,WDG拿走3-3

接下来你要拿2张牌,拿不了了,游戏结束。

你获得11021102

7 2 4
9 4 5 9 1 9 2
22

第一轮:你拿走99,WDG拿走99

第二轮:你拿走99,WDG拿走55

第三轮:你拿走44,WDG拿走2,

虽然场上还剩下一张牌,但是无论怎么分配不够给两个人,拿不了了,游戏结束。

你获得2222


本题采取捆绑测试

Subtask 1(25pts): n20n\leq 20

Subtask 2(20pts): n1000n\leq 1000

Subtask 3(15pts): Ai>0,xyA_i > 0,x \geq y

Subtask 4(15pts): Ai>0,x=1A_i>0,x = 1

Subtask 5(25pts): 无特殊限制

对于100%100\%的数据,x+yn5×105,2n,Ai106x+y\leq n\leq 5\times10^5,2\leq n,|A_i|\leq 10^6

10.13普及组模拟赛补题场

未参加
状态
已结束
规则
IOI
题目
4
开始于
2024-10-14 13:00
结束于
2024-10-22 21:00
持续时间
200 小时
主持人
参赛人数
95