#PU1358. USACO 2023 December Contest, Platinum — Problem 3. Train Scheduling

    ID: 1294 传统题 2000ms 512MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>USACO赛事:dec23来源:usaco.orgscoring:equal_test_cases二分答案线段树

USACO 2023 December Contest, Platinum — Problem 3. Train Scheduling

USACO 2023 December Contest, Platinum — Problem 3. Train Scheduling

题目描述

Note: The memory limit for this problem is 512MB, twice the default. Bessie has taken on a new job as a train dispatcher! There are two train stations: AA and BB. Due to budget constraints, there is only a single track connecting the stations. If a train departs a station at time tt, then it will arrive at the other station at time t+Tt+T (1≤T≤10121\le T\le 10^{12}). There are NN (1≤N≤50001\le N\le 5000) trains whose departure times need to be scheduled. The iith train must leave station sis_i at time tit_i or later (si∈{A,B},0≤ti≤1012s_i\in \{A, B\}, 0\le t_i\le 10^{12}). It is not permitted to have trains going in opposite directions along the track at the same time (since they would crash). However, it is permitted to have many trains on the track going in the same direction at the same time (assume trains have negligible size). Help Bessie schedule the departure times of all trains such that there are no crashes and the total delay is minimized. If train ii is scheduled to leave at time ai≥tia_i\ge t_i, the total delay is defined as ∑i=1N(ai−ti)\sum_{i=1}^N(a_i-t_i).

输入格式

The first line contains NN and TT. Then NN lines follow, where the iith line contains the station sis_i and time tit_i corresponding to the iith train.

输出格式

The minimum possible total delay over all valid schedules.

数据范围

Inputs 5-6: N≤15N \le 15 Inputs 7-10: N≤100N \le 100 Inputs 11-14: N≤500N \le 500 Inputs 15-18: N≤2000N\le 2000 Inputs 19-24: No additional constraints Problem credits: Brandon Wang

样例

样例 1

1 95
B 63
0
The only train leaves on time.

样例 2

4 1
B 3
B 2
A 1
A 3
1
There are two optimal schedules. One option is to have trains $2,3,4$ leave on
time and train $1$ leave after a one-minute delay. Another is to have trains
$1,2,3$ leave on time and train $4$ leave after a one-minute delay.

样例 3

4 10
A 1
B 2
A 3
A 21
13
The optimal schedule is to have trains $1$ and $3$ leave on time, train $2$
leave at time $13$, and train $4$ leave at time $23$.  The total delay is
$0+11+0+2=13$.

样例 4

8 125000000000
B 17108575619
B 57117098303
A 42515717584
B 26473500855
A 108514697534
B 110763448122
B 117731666682
A 29117227954
548047356974