레이팅 미적용*참고: 이 문제의 메모리 제한은 기본의 두 배인 512MB이다.*
베시가 열차 배차원이라는 새 일을 맡게 되었다! 기차역은 \(A\)와 \(B\) 두 곳이 있다. 예산 문제로 두 역을 잇는 선로는 단 하나뿐이다. 열차가 시각 \(t\)에 한 역을 출발하면 시각 \(t+T\)에 반대편 역에 도착한다 (\(1\le T\le 10^{12}\)).
출발 시각을 정해야 하는 열차가 \(N\)대 (\(1\le N\le 5000\)) 있다. \(i\)번째 열차는 역 \(s_i\)에서 시각 \(t_i\) 또는 그 이후에 출발해야 한다 (\(s_i\in \{A, B\}, 0\le t_i\le 10^{12}\)). 서로 반대 방향으로 가는 열차가 동시에 선로 위에 있는 것은 허용되지 않는다 (충돌하기 때문이다). 하지만 같은 방향으로 가는 여러 열차가 동시에 선로 위에 있는 것은 허용된다 (열차의 크기는 무시할 수 있다고 가정한다).
충돌이 없으면서 총 지연 시간이 최소가 되도록 모든 열차의 출발 시각을 정하는 것을 도와주자. 열차 \(i\)의 출발 시각을 \(a_i\ge t_i\)로 정하면, 총 지연 시간은 \(\sum_{i=1}^N(a_i-t_i)\)로 정의된다.
출제: Brandon Wang
배점
- 입력 5-6: \(N \le 15\)
- 입력 7-10: \(N \le 100\)
- 입력 11-14: \(N \le 500\)
- 입력 15-18: \(N\le 2000\)
- 입력 19-24: 추가 제약 없음
출제: Brandon Wang
첫째 줄에 \(N\)과 \(T\)가 주어진다.
다음 \(N\)개의 줄 중 \(i\)번째 줄에 \(i\)번째 열차의 역 \(s_i\)와 시각 \(t_i\)가 주어진다.
가능한 모든 유효한 시간표 중 최소 총 지연 시간을 출력한다.
1 95
B 630The only train leaves on time.
4 1
B 3
B 2
A 1
A 31There 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.
4 10
A 1
B 2
A 3
A 2113The 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\).
8 125000000000
B 17108575619
B 57117098303
A 42515717584
B 26473500855
A 108514697534
B 110763448122
B 117731666682
A 29117227954548047356974riseoj 작성
출처 올림피아드 > USACO > 2023-2024 > December > Platinum