「CF413C」Jeopardy!
‘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 ai 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.
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 integersa1, a2, …, an (1 ≤ ai ≤ 107) — the prices of the questions. The third line contains m distinct integers bi (1 ≤ bi ≤ n) — the numbers of auction questions. Assume that the questions are numbered from 1 to n.
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.
1 2 3 |
4 1 1 3 7 5 3 |
1 |
18 |
1 2 3 |
3 2 10 3 8 2 3 |
1 |
40 |
1 2 3 |
2 2 100 200 1 2 |
1 |
400 |
题意
有n道题,每道题有一个分值,在回答问题时你可以选择提升其中m道题(给定的m道题)的分值
提升的上限是你当前的得分,制定一个顺序以及策略使得总分最高
题解
首先不能提升分数的题先全部加入答案
然后把剩下的题从大到小排序
尽量多得分即可(即要么ans*=2,要么ans+=a[i],比较当前ans与a[i]大小)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
#include<cstdio> #include<iostream> #include<algorithm> #define inf 0x7fffffff int n,m,tot; long long ans; int a[101],c[101]; bool b[101]; using namespace std; int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)scanf("%d",&a[i]); for(int i=1;i<=m;i++){int x;scanf("%d",&x);b[x]=1;} for(int i=1;i<=n;i++) if(!b[i])ans+=a[i]; else c[++tot]=a[i]; sort(c+1,c+tot+1); for(int i=tot;i>0;i--) if(ans<c[i])ans+=c[i]; else ans<<=1; printf("%I64d",ans); return 0; } |
分类目录
热门文章
- 12043NOIP1999拦截导弹
- 11615「BZOJ3261」最大异或和
- 11379NOIP2010导弹拦截
- 98862017 训练赛 1 by hzwer
- 9505「百度之星2017」程序设计大赛 初赛(B)
- 8430「JoyOI1048」田忌赛马
- 8421NOIP2010引水入城
- 82782017ACM萧山训练第4场(CTUO 2015)
- 82592017ACM萧山训练第3场(World Final 2013)
- 8123「CF718X」Codeforces Round #373 (Div. 1)
- 7782「BZOJ3709」[PA2014] Bohater
- 7741NOI2010 超级钢琴
- 7706「BZOJ1046」[HAOI2007] 上升序列
- 7704「BZOJ1150」[CTSC2007] 数据备份Backup
- 7597「BZOJ2811」[Apio2012] Guard
- 7492「BZOJ2288」「POJ Challenge」生日礼物
- 7331「BZOJ3166」[HEOI2013] Alo
- 7195「BZOJ2151」种树
- 7179「BZOJ3105」[CQOI2013] 新Nim游戏
- 7010「BZOJ4027」[HEOI2015] 兔子与樱花
- 6853NOIP2012国王游戏
- 6819「CF1280X」Codeforces Round #607 (Div. 1)
- 6803「BZOJ1086」[SCOI2005] 王室联邦
- 6756NOIP2007纪念品分组
- 6755NOI2014随机数生成器
- 6621「CF538X」Codeforces Round #300
- 6582「BZOJ1043」[HAOI2008] 下落的圆盘
- 6550POJ训练记录2
- 65052017ACM萧山训练第5场(2016 Pacific Northwest - Division 1)
- 62622015 ACM / ICPC EC - Final
- 6201「codechef」January Challenge 2015
- 6096NOIP2004合并果子
- 6079「BZOJ1229」[USACO2008 Nov] toy 玩具
- 6070NOI2009诗人小G
近期评论
- 匿名发表在《hzwer.com 博客导航》
- 匿名发表在《hzwer.com 博客导航》
- 匿名发表在《hzwer.com 博客导航》
- 匿名发表在《留言板》
- 匿名发表在《你好,世界》