레이팅 미적용베시가 하이킹을 떠난다! 베시가 현재 지나고 있는 등산로는 \(1\ldots N\)으로 이름 붙은 \(N\)개의 체크포인트로 이루어져 있다(\(1\le N\le 10^5\)).
구매할 수 있는 티켓이 \(K\)장(\(1\le K\le 10^5\)) 있다. \(i\)번째 티켓은 체크포인트 \(c_i\)(\(1\le c_i\le N\))에서 가격 \(p_i\)(\(1\le p_i\le 10^9\))에 구매할 수 있으며, 체크포인트 구간 \([a_i,b_i]\)(\(1\le a_i\le b_i\le N\)) 전체에 대한 접근 권한을 제공한다. 어떤 체크포인트에 들어가기 전에, 베시는 그 체크포인트에 대한 접근을 허용하는 티켓을 미리 구매해 두어야 한다. 베시가 어떤 체크포인트에 접근할 수 있게 되면, 이후 언제든지 그곳으로 돌아올 수 있다. 접근 권한이 있는 두 체크포인트 사이는 번호의 차이가 1인지 여부와 관계없이 이동할 수 있다.
각 \(i\in [1,N]\)에 대해, 베시가 처음에 체크포인트 \(i\)에만 접근할 수 있을 때 체크포인트 \(1\)과 \(N\) 모두에 대한 접근 권한을 구매하는 데 필요한 최소 총 가격을 출력하라. 불가능하다면 대신 \(-1\)을 출력한다.
출제자: Benjamin Qi
배점
- 테스트 케이스 1-7은 \(N,K\le 1000\)을 만족한다.
- 테스트 케이스 8-19는 추가 제약이 없다.
출제자: Benjamin Qi
첫째 줄에 \(N\)과 \(K\)가 주어진다.
다음 \(K\)개의 줄에 각 \(1\le i\le K\)에 대해 네 정수 \(c_i\), \(p_i\), \(a_i\), \(b_i\)가 주어진다.
각 체크포인트마다 한 줄씩, 총 \(N\)개의 줄을 출력한다.
7 6
4 1 2 3
4 10 5 6
2 100 7 7
6 1000 1 1
5 10000 1 4
6 100000 5 6-1
-1
-1
1111
10100
110100
-1If Bessie starts at checkpoint \(i=4\), then one way for Bessie to purchase access
to checkpoints \(1\) and \(N\) is as follows:
- Purchase the first ticket at checkpoint \(4\), giving Bessie access to checkpoints \(2\) and \(3\).
- Purchase the third ticket at checkpoint \(2\), giving Bessie access to checkpoint \(7\).
- Return to checkpoint \(4\) and purchase the second ticket, giving Bessie access to checkpoints \(5\) and \(6\).
- Purchase the fourth ticket at checkpoint \(6\), giving Bessie access to checkpoint \(1\).
riseoj 작성
출처 올림피아드 > USACO > 2021-2022 > December > Platinum