시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 295 | 95 | 74 | 45.122% |
포천 주민들은 여러 버스 정류장에서 버스를 기다리고 있다. 하지만 안타깝게도 버스는 이 모든 사람들을 수용할 수 있는 크기가 되지 못한다.
문제는 정류장의 개수 N과 M개의 그룹에 대해 현재 기다리는 정류장 번호와 내릴 정류장 번호가 주어지면 1번 정류장에서 출발하여 N번 정류장까지 운행할 때 최대 태울 수 있는 인원을 구하는 것이다. 단, 버스는 1, 2, …, N번 정류장 순서로 방문한다.
첫 줄에는 그룹의 수 K(1 ≤ K ≤ 50,000)와 정류장 개수 N(1 ≤ N ≤ 20,000)과 버스의 최대 수용 인원 C(1 ≤ C ≤ 100)가 공백으로 구분되어 주어진다. 두 번째 줄부터 K+1번째 줄까지 각 줄에 대해 K개의 그룹에 대한 정보가 담긴 Si, Ei, Mi가 주어지는데 이는 이 그룹은 총 Mi명이고 Si번 정류장에서 출발하여 Ei번 정류장에서 내릴려고 한다는 의미이다.
첫 줄에 최대 수송 인원을 출력한다.
8 15 3 1 5 2 13 14 1 5 8 3 8 14 2 14 15 1 9 12 1 12 15 2 4 6 1
10
버스가 1번->5번으로 가는 2명인 그룹과 5번->8번으로 가는 3명인 그룹, 8번->14번으로 가는 2명인 그룹, 9번->12번으로 가는 1명인 그룹, 13번->14번으로 가는 1명인 그룹, 14번->15번으로 가는 1명인 그룹을 태우면 총 10명을 수송한 셈이 된다.