P16789 [Lanqiao Cup 2026 National A] Core Task Scheduling

Xiao Lan is a project manager at a company and needs to handle a large number of tasks every day. Now the company has a total of $N$ tasks to complete, and each task takes one day. Days start from day $1$ and are numbered by positive integers as day $1$, day $2$, day $3$, and so on. Xiao Lan can complete at most one task per day, and may also leave a day with no task scheduled. Each task has a deadline $t$ and a value $w$. If the task is completed on day $t$ or earlier, it can create value $w$ for the company; if it exceeds the deadline, the task becomes invalid and can no longer be completed. Among these tasks, some are marked as core tasks. The company requires that when Xiao Lan makes a schedule, they must first maximize the number of completed core tasks; among all schedules that satisfy this, they should then maximize the total value of all completed tasks. Now, please help Xiao Lan compute: the maximum number of core tasks that can be completed, and under the condition that the number of completed core tasks is maximized, the maximum total value that can be obtained.

The first line contains a positive integer $N$, indicating the total number of tasks. The next $N$ lines each contain three integers $t_i, w_i, \text{is\_key}_i$, representing the deadline, value, and whether the $i$-th task is a core task, respectively. Here, $\text{is\_key}_i = 1$ means it is a core task, and $\text{is\_key}_i = 0$ means it is a normal task.

Output one line containing two integers, representing the maximum number of core tasks that can be completed, and under this condition, the maximum total value that can be obtained.

### Sample Explanation To prioritize completing as many core tasks as possible, Xiao Lan can schedule task $2$ on day $1$ and task $1$ on day $3$. In this way, they can complete $2$ core tasks, with a total value of $15$. While keeping the completion of $2$ core tasks, they can also schedule task $3$ on day $2$, making the total value $5 + 100 + 10 = 115$. The deadline of task $4$ is day $1$, and it can no longer be completed on time. ### Constraints and Notes for Test Cases For $30\%$ of the test cases, $1 \le N \le 1000$, $1 \le t_i \le 1000$. For all test cases, $1 \le N \le 2 \times 10^5$, $1 \le t_i \le 10^9$, $1 \le w_i \le 10^9$. Translated by ChatGPT 5