题目 5008

游戏通关

查看题解 ↗GitHub ↗如何评测
题号
5008
时间限制
1000 ms
内存限制
256 MB
标签
贪心
来源
信息学奥赛一本通 · 高手训练篇·一、基础算法(高手训练)

【题目描述】

XY在玩一个包含NN个任务的游戏。每个任务完成时限为TiT_i(你可以认为还没开始做任务时的时间为00),奖励为WiW_i。由于XY技术的娴熟以及任务的简单,对于每个任务,他都可以在一个单位时间内完成。 XY想要知道他能够获得的最多的奖励。

【输入】

第一行一个整数NN,表示需要完成的任务数目。 接下来NN行,每行两个整数T、WT、W,分别表示完成这个任务的最后期限和完成这个任务后获得的奖励。

【输出】

输出数据有且仅有一行,只包含一个整数,表示最多获得的奖励。

【输入样例】

文本
2
1 5
1 4

【输出样例】

文本
5

【提示】

【样例输入2】

文本
5
2 3
1 2
4 5
1 3
3 4

【样例输出2】

文本
15

【样例解释2】 对于样例2,XY可以选择完成任务1、3、41、3、4 和55,这样他可以获得奖励1515。 【数据规模及约定】 对于10%的数据,N≤100,Ti≤100,Wi≤2000N≤100,T_i≤100,W_i≤2000。 对于30%的数据,N≤1000,Ti≤5000,Wi≤2000N≤1000,T_i≤5000,W_i≤2000。 对于50%的数据,N≤10000,Ti≤20000,Wi≤2000N≤10000,T_i≤20000,W_i≤2000。 对于100%的数据,N≤200000,Ti≤200000,Wi≤2000N≤200000,T_i≤200000,W_i≤2000。

文本
5\n2 3\n1 2\n4 5\n1 3\n3 4
文本
15

数据下载

题目 5008 的公开数据

正在读取文件列表…

常用命令

题目 5008 的 ROJ 命令

以下命令默认使用全局安装的 ROJ Skill,请在终端中直接执行;如果修改过 AGENT_HOME,请将命令中的 ~/.agents 替换为对应目录。