Problems
베시는 새로운 일로 열차 디스패처로 일하게 되었습니다! 두 역이 있습니다: A 역과 B 역. 예산 제약으로 두 역을 연결하는 단일 트랙만 있습니다. 만약 어떤 열차가 시간 t에 역을 출발하면, 그 열차는 t+T (1≤T≤10^12)에 다른 역에 도착합니다.
시간표를 작성해야 하는 N (1≤N≤5000)대의 기차가 있습니다. i번째 기차는 역 si에서 시간 ti에 출발해야 합니다 (si∈{A,B}, 0≤ti≤10^12). 반대 방향으로 이동하는 열차가 동시에 트랙을 따라가면 안 되므로 (충돌이 발생할 수 있음), 같은 방향으로 이동하는 여러 기차가 동시에 트랙을 따라갈 수는 있습니다 (열차는 무시할 수 있는 크기를 갖고 있다고 가정).
베시가 모든 기차의 출발 시간을 정해야 합니다. 충돌이 발생하지 않으면서 전체 지연 시간이 최소화되도록 도와주세요. 기차 i가 시간 ai≥ti에 출발하도록 예정된 경우, 전체 지연 시간은 ∑Ni=1(ai−ti)로 정의됩니다.
Bessie has taken on a new job as a train dispatcher! There are two train stations: A and B. Due to budget constraints, there is only a single track connecting the stations. If a train departs a station at time t, then it will arrive at the other station at time t+T (1≤T≤10^12).
There are N (1≤N≤5000) trains whose departure times need to be scheduled. The ith train must leave station si at time ti or later (si∈{A,B},0≤ti≤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 egligible size).
Help Bessie schedule the departure times of all trains such that there are no crashes and the total delay is minimized. If train i is scheduled to leave at time ai≥ti, the total delay is defined as ∑Ni=1(ai−ti).
Input
첫 번째 줄에 N과 T가 주어집니다. 그런 다음 N개의 줄이 따릅니다. i번째 줄에는 i번째 기차에 해당하는 역 si와 시간 ti가 포함되어 있습니다.
The first line contains N and T.
Then N lines follow, where the ith line contains the station si and time ti corresponding to the ith train.
Output
모든 유효한 일정을 대상으로 최소 가능한 총 지연 시간입니다.
The minimum possible total delay over all valid schedules.
Example #1
1 95
B 63
0
Example #2
4 1
B 3
B 2
A 1
A 3
1
두 가지 최적의 일정이 있습니다. 하나는 기차 2, 3, 4가 제때 출발하고 기차 1은 1분 지연 후 출발하는 것입니다. 또 다른 옵션은 기차 1, 2, 3이 제때 출발하고 기차 4는 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.
Example #3
4 10
A 1
B 2
A 3
A 21
13
최적의 일정은 기차 1과 3이 제때 출발하고 기차 2는 13시에, 기차 4는 23시에 출발하는 것입니다. 전체 지연은 0+11+0+2=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.
Example #4
8 125000000000
B 17108575619
B 57117098303
A 42515717584
B 26473500855
A 108514697534
B 110763448122
B 117731666682
A 29117227954
548047356974
You must sign in to write code.