P3212 [HNOI2011] Task Scheduling

There are $n$ tasks and two machines, A and B. Each task must be processed on both machines. The $i$-th task requires time $a_i$ on machine A and time $b_i$ on machine B. The goal is to finish all tasks on both A and B while minimizing the total time to complete all tasks. However, some tasks have restrictions on whether they must be processed on A first or on B first. Based on this, all tasks are divided into three categories: 1. The task must be processed on machine A first, then on machine B. 2. The task must be processed on machine B first, then on machine A. 3. The task has no restriction and may be processed on machine A first or on machine B first. Given each task’s category and its processing times on machines A and B, find the minimum total time required to finish all tasks according to the rules.

The first line contains a single positive integer $n$, the number of tasks. Each of the next $n$ lines contains three space-separated positive integers $t_i, a_i, b_i$, denoting the category of task $i$ (categories $1$, $2$, and $3$ are as defined above) and the processing times of task $i$ on machines A and B, respectively.

Output a single integer, the minimum total time required to finish all tasks.

Sample 1 Explanation: One optimal scheduling plan is: On machine A, schedule the tasks in order: Task $1\ (0\to 5)$, task $2\ (5\to 11)$, task $3\ (11\to 13)$; On machine B, schedule the tasks in order: Task $3\ (0 \to 6)$, task $1\ (6 \to 13)$, task $2\ (13 \to14)$, so the total time required to finish all tasks is $14$. Constraints: For $100\%$ of the testdata, it is guaranteed that $1 \le n \le 20$, $1 \le a_i \le 10^3$, $1 \le t_i \le 3$, and the number of tasks with $t_i = 3$ does not exceed $10$. Translated by ChatGPT 5