시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 77 | 15 | 10 | 21.739% |
N(1 ≤ N ≤ 10,000)개의 정류장을 지나는 버스가 있다. 정류장은 차례로 1, 2, …, N번의 번호가 붙어 있고, 버스는 1번 정류장에서 출발하여 N번 정류장까지 간 후, 다시 1번 정류장으로 돌아오게 된다.
버스회사에서는 주기적으로 1번 정류장에서 버스를 출발시켜서 모든 손님들이 버스를 이용할 수 있도록 하고 있었는데, 겨울철에 눈이 많이 오는 바람에 한 대의 버스밖에 운행하지 못 하게 되었다. 불행 중 다행으로 회사에서는 고객들이 버스를 이용하는 구간을 K(1 ≤ K ≤ 50,000)개 조사해 둔 상태이다.
버스는 최대 C(1 ≤ C ≤ 100)명을 태울 수 있다. 회사 측에서는 사전에 조사해 둔 자료를 바탕으로, 한 바퀴를 도는(1번 정류장에서 N번 정류장까지 갔다가 다시 1번 정류장으로 돌아오는) 동안 가급적이면 많은 고객들을 목적지까지 태워 주려고 한다. 각 정류장에서 버스는 사람을 내려 줄 수도 있고, 사람을 태울 수도 있다. 단, 버스에 한 밴 태운 고객들은 목적지에 도착하기 전에는 내려줄 수 없다.
목적지까지 태워줄 수 있는 고객의 최대 수를 구하는 프로그램을 작성하시오.
첫째 줄에 세 정수 K, N, C가 주어진다. 다음 K개의 줄에는 고객들의 버스 이용 구간을 나타내는 세 정수 S, E(1 ≤ S, E ≤ N), M(1 ≤ M ≤ C)이 주어진다. S와 E는 서로 다르며, 이는 S번 정류장에서 E번 정류장까지 가려는 고객이 M명 있다는 의미이다.
첫째 줄에 답을 출력한다.
4 8 3 1 3 2 2 8 3 4 7 1 8 3 2
6
1번 정류장에서 3번 정류장으로 가는 고객을 두 명 태운다. 2번 정류장에서는 8번 정류장으로 가는 고객을 한 명 태운다(세 명을 다 태울 필요는 없다). 3번 정류장에서 두 명의 고객을 내려 주고, 4번 정류장에서는 7번 정류장으로 가는 고객을 한 명 태운다. 7번 정류장에서 한 명의 고객을 내려 주고, 8번 정류장에서 남은 한 명의 고객을 내려 준 뒤, 3번 정류장으로 가는 고객을 두 명 태운다. 이 고객들을 3번 정류장에 내려 주고, 다시 1번 정류장으로 돌아온다.
Olympiad > USA Computing Olympiad > 2005-2006 Season > USACO October 2005 Contest > Gold ?번