P16195 [ROIR 2014 Day 1] Olympiad

In an inter-regional robot programming Olympiad, the contest has only one round and uses a special way to release problems. The problems are not given to contestants all at once; instead, they are released one by one in order. Problem $i$ $(1 \le i \le n)$ becomes available at time $s_i$ minutes. Whenever a problem appears, the contestant must immediately decide whether to solve it. If they decide to solve it, they have $t_i$ minutes to submit an answer, and during this time they cannot switch to solve other problems. If they skip this problem, they can never come back to solve it later. After the time for the current solved problem runs out, the contestant can immediately start solving new problems that are available at that same moment (if any), or wait until the next problem appears. For each correctly solved problem, the contestant earns $c_i$ points. Arthur represents a regional AI center in the contest. He knows that this contest tests not only problem-solving ability, but also strategy— which problems to solve and which to skip. Before the contest starts, all contestants know each problem’s release time, solving time, and score. Arthur is a genius and is guaranteed to finish and submit any problem he chooses within the given time. Write a program to help Arthur compute the maximum score he can get, and which problems he should solve.

The first line contains an integer $n$ $(1 \le n \le 100\,000)$, the number of problems in the contest. The next $n$ lines each contain three integers: $s_i$ (the release time of problem $i$, in minutes), $t_i$ (the solving time, in minutes), and $c_i$ (the points earned for solving it). All numbers satisfy $1 \le s_i, t_i, c_i \le 10^9$.

The first line output an integer: the maximum score Arthur can obtain. The second line output an integer $m$: the number of problems Arthur solves under an optimal strategy. The third line output $m$ integers separated by spaces: the indices of these problems (starting from $1$, numbered in the input order), in the order Arthur solves them. If there are multiple optimal strategies, output any one of them.

In the first sample, Arthur can finish all problems and get $3$ points. In the second sample, solving the last problem gives $3$ points, which is better than solving only the first two problems for $2$ points. ### Scoring For the $30$-point testdata, all $c_i$ are the same and $n \le 1000$. For the $50$-point testdata, all $c_i$ are the same. For the $50$-point testdata, $n \le 1000$. Translation source: GPT 4.1 mini. Translated by ChatGPT 5