logo AlgoBeat OnlineJudge
登录 注册

#216145. [ROIR 2014 Day 1] Olympiad 奥赛

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

题目描述

在一次跨区域机器人编程奥林匹克竞赛中,比赛只进行一轮,而且采用了特别的出题方式。题目不是一开始全部发给选手,而是按顺序陆续放出。第 道题会在时间点 分钟时开放给选手。每当一道题出现时,选手必须立刻决定是否要做它。如果决定做,就有 分钟的时间提交答案,在这段时间内不能切换去做其他题。如果放弃了这道题,之后就不能再回头做它。等当前做的题目时间用完后,选手可以马上开始做同一时刻开放的新题(如果有的话),或者等下一道题出现。每做对一道题,选手能获得 分。

阿图尔代表一个区域人工智能中心参加比赛,他知道这场比赛不仅考验解题能力,更考验选题策略——哪些题该做,哪些该跳过。比赛开始前,所有选手都知道每道题的开放时间、解题时长和分值。阿图尔是个天才学生,保证只要选择做某题,就一定能在规定时间内完成并提交。

请你写个程序,帮阿图尔算出他最多能拿多少分,以及他应该做哪些题。

输入格式

第一行一个整数 ,表示比赛中的题目数量。

接下来 行,每行三个整数:(第 题开放时间,单位分钟)、(解题时间,单位分钟)、(做对该题能得的分数)。所有数均满足

输出格式

第一行输出一个整数——阿图尔能拿到的最高分数。

第二行输出一个整数 ——最优策略下阿图尔要做的题目数量。

第三行输出 个用空格分开的整数,表示这些题目的编号(从 开始,按输入顺序编号),顺序为阿图尔做题的先后顺序。

如果有多个最优方案,输出其中任意一个即可。

样例

样例输入 1

2
1 1 1
2 2 2

样例输出 1

3
2
1 2

样例输入 2

3
1 2 1
3 2 1
2 4 3

样例输出 2

3
1
3

数据范围与提示

在第一个样例中,阿图尔能做完所有题,拿到 分。

在第二个样例中,阿图尔做最后一道题能拿 分,比只做前两道题拿 分更划算。

评分

对于 分的数据,所有 相同且

对于 分的数据,所有 相同。

对于 分的数据,

翻译来源:GPT 4.1 mini。