A90538.「USACO 2023.12 Platinum」Train Scheduling

题目译自 USACO 2023 December Contest, Platinum Problem 3. Train Scheduling

Bessie 有了一份新工作：火车调度员！有两个火车站 $A$ 和 $B$。由于预算限制，这两个车站之间只有一条轨道。如果火车在时刻 $t$ 离开火车站，那么它会在时刻 $t+T$ 到达另一个火车站。

有 $N$ 趟火车的出发时间需要被安排。第 $i$ 趟火车必须在时刻 $t_i$ 或之后离开 $s_i$ 站。不允许火车同时在轨道上相向而行（因为它们会相撞）。然而，允许轨道上有许多火车同时向同一方向行驶（假设列车的大小可以忽略不计）。

请帮 Bessie 安排所有火车的出发时间，满足火车不会相撞，并且总晚点时间最小。如果火车 $i$ 计划在时刻 $a_i\ge t_i$ 出发，则总晚点时间定义为 $\sum_{i=1}^N (a_i-t_i)$。

第一行包含两个整数 $N\ (1\le N\le 5000)$ 和 $T\ (1\le T\le 10^{12})$。

接下来 $N$ 行，第 $i$ 行表示第 $i$ 趟火车的始发站 $s_i\ (s_i\in\{\texttt{A},\texttt{B}\})$ 和预计出发时刻 $t_i\ (0\le t_i\le 10^{12})$。

输出一行，表示对于所有合法调度方案，最小的总晚点时间。

• 测试点 $5\sim 6$：$N\le 15$
• 测试点 $7\sim 10$：$N\le 100$
• 测试点 $11\sim 14$：$N\le 500$
• 测试点 $15\sim 18$：$N\le 2000$
• 测试点 $19\sim 24$：无附加限制

Problem credits: Brandon Wang