레이팅 미적용농부 존은 소젖을 짤 때 양동이를 배정하는 방식을 바꿀까 고민하고 있다. 그는 이렇게 하면 결국 전체 양동이 수를 적게 유지할 수 있을 것이라 생각하지만, 정확히 몇 개가 필요한지는 잘 모른다. 그를 도와주자!
농부 존에게는 \(N\)마리의 소가 있다 (\(1 \leq N \leq 100\)). 소들은 편의상 \(1 \ldots N\)번으로 번호가 매겨져 있다. \(i\)번째 소는 시각 \(s_i\)부터 시각 \(t_i\)까지 젖을 짜야 하고, 젖을 짜는 동안 \(b_i\)개의 양동이가 필요하다. 여러 소의 젖을 동시에 짜게 될 수도 있는데, 그런 경우 같은 양동이를 함께 사용할 수 없다. 즉, 소 \(i\)의 착유에 배정된 양동이는 시각 \(s_i\)부터 시각 \(t_i\) 사이에는 다른 소의 착유에 사용될 수 없다. 물론 이 시간 구간 밖에서는 그 양동이를 다른 소에게 사용할 수 있다. 일을 단순하게 하기 위해, 농부 존은 어느 시점에서든 착유가 시작되거나 끝나는 소가 최대 한 마리가 되도록 해 두었다 (즉, \(s_i\)들과 \(t_i\)들은 모두 서로 다르다).
농부 존의 창고에는 1, 2, 3, ... 순서로 번호표가 붙은 양동이들이 있다. 그의 현재 착유 전략에서는, 어떤 소 (예를 들어 소 \(i\))의 착유가 시작될 때마다 (시각 \(s_i\)에), 농부 존은 창고로 달려가 사용 가능한 것 중 번호가 가장 작은 \(b_i\)개의 양동이를 가져와 소 \(i\)의 착유에 배정한다.
모든 소의 젖을 성공적으로 짜기 위해 농부 존이 창고에 보관해야 하는 양동이가 총 몇 개인지 구하여라.
출제자: Brian Dean
출제자: Brian Dean
입력의 첫째 줄에 \(N\)이 주어진다. 다음 \(N\)개의 줄에는 각각 소 한 마리를 나타내는 수 \(s_i\), \(t_i\), \(b_i\)가 공백으로 구분되어 주어진다. \(s_i\)와 \(t_i\)는 모두 \(1 \ldots 1000\) 범위의 정수이고, \(b_i\)는 \(1 \ldots 10\) 범위의 정수이다.
농부 존에게 필요한 양동이의 총 개수를 정수 하나로 출력한다.
blist.in · 출력을 쓸 파일 blist.out3
4 10 1
8 13 3
2 6 24In this example, FJ needs 4 buckets: He uses buckets 1
and 2 for milking cow 3 (starting at time 2). He uses bucket 3 for milking cow
1 (starting at time 4). When cow 2 arrives at time 8, buckets 1 and 2 are now
available, but not bucket 3, so he uses buckets 1, 2, and 4.
riseoj 작성
출처 올림피아드 > USACO > 2018-2019 > December > Bronze