传统题 文件IO:schedule 1000ms 256MiB

Schedule

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

读写要求

本题采用文件读写,请在提交代码时使用正确的文件名,否则会导致 RE

输入文件:schedule.in

输出文件:schedule.out

题目描述

农夫约翰有很多工作要做!为了高效地经营农场,他必须从他所做的每一项工作中赚取利润,每项工作只需要一个时间单位。

他的工作日从时间 00 开始,总共有 10910^9 个时间单位。他目前可以从 NN 项工作中选择要做的工作,这些工作被方便地编号为 11NN

虽然理论上他有可能完成所有 NN 项工作,但实际上这是极不可能的,因为他在任何一个时间单位内只能完成一项工作,而截止日期通常会导致他无法完成所有任务。

ii 项工作的截止时间为 DiD_i。如果他在截止时间前完成第 ii 项工作(如果当前时间为 tt,那么仅当 Di>tD_i>t 的时候他能做这个任务,完成后 tt+1t\rightarrow t+1),他将获得 PiP_i 的利润。

给定一系列工作和截止日期,FJ 能够获得的最大总利润是多少?答案可能无法容纳在 3232 位整数中。

输入格式

第一行一个整数 NN

接下来 NN 行,每行两个整数 Di,PiD_i,P_i

输出格式

输出一个整数,表示最大总利润。

数据范围

1N1051\le N\le 10^51Di,Pi1091\le D_i,P_i\le 10^9

输入输出样例

3
2 10
1 5
1 7
17

说明

在时间 11 完成工作 331,71,7),在时间 22 完成工作 112,102,10)以最大化收益,最后收益为 7+10=177+10=17

周赛#1028(div2)

未参加
状态
已结束
规则
IOI
题目
5
开始于
2026-5-30 19:00
结束于
2026-5-30 20:30
持续时间
1.5 小时
主持人
参赛人数
18