P16195 [ROIR 2014 Day 1] Olympiad 奥赛

在一次跨区域机器人编程奥林匹克竞赛中，比赛只进行一轮，而且采用了特别的出题方式。题目不是一开始全部发给选手，而是按顺序陆续放出。第 $i\ (1 \le i \le n)$ 道题会在时间点 $s_i$ 分钟时开放给选手。每当一道题出现时，选手必须立刻决定是否要做它。如果决定做，就有 $t_i$ 分钟的时间提交答案，在这段时间内不能切换去做其他题。如果放弃了这道题，之后就不能再回头做它。等当前做的题目时间用完后，选手可以马上开始做同一时刻开放的新题（如果有的话），或者等下一道题出现。每做对一道题，选手能获得 $c_i$ 分。 阿图尔代表一个区域人工智能中心参加比赛，他知道这场比赛不仅考验解题能力，更考验选题策略——哪些题该做，哪些该跳过。比赛开始前，所有选手都知道每道题的开放时间、解题时长和分值。阿图尔是个天才学生，保证只要选择做某题，就一定能在规定时间内完成并提交。 请你写个程序，帮阿图尔算出他最多能拿多少分，以及他应该做哪些题。

第一行一个整数 $n\ (1 \le n \le 100\,000)$，表示比赛中的题目数量。 接下来 $n$ 行，每行三个整数：$s_i$（第 $i$ 题开放时间，单位分钟）、$t_i$（解题时间，单位分钟）、$c_i$（做对该题能得的分数）。所有数均满足 $1 \le s_i, t_i, c_i \le 10^9$。

第一行输出一个整数——阿图尔能拿到的最高分数。 第二行输出一个整数 $m$——最优策略下阿图尔要做的题目数量。 第三行输出 $m$ 个用空格分开的整数，表示这些题目的编号（从 $1$ 开始，按输入顺序编号），顺序为阿图尔做题的先后顺序。 如果有多个最优方案，输出其中任意一个即可。

在第一个样例中，阿图尔能做完所有题，拿到 $3$ 分。 在第二个样例中，阿图尔做最后一道题能拿 $3$ 分，比只做前两道题拿 $2$ 分更划算。 ### 评分 对于 $30$ 分的数据，所有 $c_i$ 相同且 $n\le 1000$。 对于 $50$ 分的数据，所有 $c_i$ 相同。 对于 $50$ 分的数据，$n\le 1000$。 翻译来源：GPT 4.1 mini。