Problem 4040 --最长游览

4040: 最长游览

"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $13$ 正确数量 $7$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签
在梦境中,Aoi来到了Byteland。 Byteland为了促进旅游产业,在各地开设了许多观光巴士的线路。这里的观光巴士采取一种奇特的收费 模式: • 当游客入境Byteland时,发放一张交通卡。卡上记载着一个数c,开始时c = 0。 • 每条巴士路线有一个编号pi。如果游客打算乘坐编号为pi的巴士,上车时需要刷交通卡,卡上的数 将从c变成c or pi,其中or是按位或运算。 • 游客可以自由多次乘坐不同的观光巴士。例如,游客乘坐了p1、p2和p4三种巴士,则交通卡上的数 字应为p1 or p2 or p4。 • 当游客离开Byteland时,需要交等同于卡上记载的数c的交通费。 每条巴士路线还有行程长度di。Aoi的交通费预算是k,她想知道,在不超过预算的前提下,能够搭乘观 光巴士的总里程(也就是搭乘的巴士的行程长度的和)最大是多少?为了尽可能观赏不同的景色,多次 搭乘同一条路线的巴士不重复计算里程。 
输入的第1行包含2个整数n, k(1 ≤ n ≤ 105 , 0 ≤ k < 2 30),依次表示巴士路线的数目和Aoi的交通费预 算。 接下来n行,每行包含2个整数pi , di(0 ≤ pi < 2 30 , 1 ≤ di ≤ 109 ),描述一条巴士路线。

输出1行1个整数,表示最大的总里程。 

对于前30%的数据,n, k < 2048。 

3 12
10 10
4 6
3 5
15
在样例中,Aoi可以选择乘坐路线1和路线3,最终交通费为10 or 3 = 11。 在大多数程序设计语言中,按位或运算的运算符是|。 

推荐代码 查看4040 所有题解 上传题解视频得图灵币

本题记录 用 户(点击查看用户) 运行号(点击购买题解) 时 间
算法最快[$2 $ms] 夜雨 1097551 2024-04-23 21:28:31
内存最少[$2180 $KB] AOJ大管家 1091771 2024-04-07 10:53:46
第一AC AOJ大管家 960487 2023-04-29 22:41:44
第一挑战 AOJ大管家 960487 2023-04-29 22:41:44

赛题来源/所属竞赛 N/A

竞赛编号 竞赛名称 竞赛时间 访问比赛