/ Vijos / 题库 /

智力游戏

智力游戏

时间限制:1秒  内存限制:256M


【题目描述】

  小H同学报名参加智力大冲浪节目。本次挑战赛吸引了众多参赛者,比赛规则如下:
  有 \(N\) 个智力小游戏,每个游戏花一个单位时间完成。从 0 时刻开始,有 \(10^9\) 个单位时间。在任一时刻,挑战者都可以选择编号为 \(1\) 到 \(N\) 的 \(N\) 个游戏中的任意一个游戏来完成。 因为每个游戏都有一个完成的截止日期,所以他很难有时间完成所有 \(N\) 个游戏,虽然还是有可能。
  对于第 \(i\) 个游戏,有个截止时间 \(D_i (1≤D_i≤10^9)\),如果他可以完成这个游戏,那么他可以获利 \(P_i(1≤P_i≤10^9)\)。 在给定的游戏利润和截止时间下,小H能够获得的利润最大为多少呢?答案可能会超过64位整型。

【输入格式】

  第一行是一个整数 \(N\)。
  第 \(2..N+1\) 行:第 \(i+1\) 行有两个用空格分开的整数:\(D_i\) 和 \(P——i\)。

【输出格式】

  输出一行,里面有一个整数,表示最大获利值。

【输入输出样例】

 Input

3
2 10
1 5
1 7

 Output

17

【数据范围】

  对于所有测试数据有:\(1≤N≤500000\)。

【来源】

   Mr.he

信息

ID
2855
难度
(无)
分类
贪心 | 数据结构 | 队列 点击显示
标签
(无)
递交数
0
已通过
0
通过率
?
被复制
2
上传者