logo AlgoBeat OnlineJudge
登录 注册

#216788. [蓝桥杯 2026 国 A] 核心任务调度

内存限制:512 MiB 时间限制:2000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

小蓝是某公司的项目经理,每天都需要处理大量任务。现在公司一共有 个任务需要完成,每个任务都需要花费一天时间。

天数从第 天开始,按正整数依次编号为第 天、第 天、第 天,依此类推。小蓝每天至多完成一个任务,也可以在某一天不安排任何任务。

每个任务有一个截止时间 和一个价值 。如果该任务在第 天或更早完成,就可以为公司创造 的价值;如果超过截止时间,该任务就会失效,不能再被完成。

这些任务中,有一部分被标记为核心任务。公司要求小蓝制定调度方案时,必须先让完成的核心任务数量尽可能多;在所有满足这一要求的方案中,再让完成任务的总价值尽可能大。

现在,请你帮助小蓝计算:最多能完成多少个核心任务,以及在完成核心任务数量最多的前提下,能够获得的最大总价值。

输入格式

第一行包含一个正整数 , 表示任务总数。

接下来 行,每行包含三个整数 , 分别表示第 个任务的截止时间、价值以及是否为核心任务。

其中, 表示核心任务, 表示普通任务。

输出格式

输出一行,包含两个整数,分别表示最多能完成的核心任务数量,以及在此前提下能获得的最大总价值。

样例

样例输入 1

4
3 10 1
1 5 1
2 100 0
1 100 0

样例输出 1

2 115

数据范围与提示

【样例说明】

为了优先完成尽可能多的核心任务,小蓝可以将任务 安排在第 天,将任务 安排在第 天。这样可以完成 个核心任务,总价值为

在保持完成 个核心任务的前提下,还可以将任务 安排在第 天,使总价值变为 。任务 的截止时间为第 天,此时已经无法再按时完成。

【评测用例规模与约定】

对于 的评测用例,,

对于所有评测用例,, ,