페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#4091

The Bucket List 2s 512MB

문제

Farmer John은 젖소들에게 착유용 양동이를 배분하는 방식을 바꾸는 것을 고려하고 있습니다. 그는 이로 인해 결국 전체적으로 적은 수의 양동이만 필요하게 될 것이라고 생각하지만, 정확히 몇 개가 필요한지는 확신하지 못합니다. 도와주시기 바랍니다!

Farmer John에게는 N마리의 소가 있으며(1 \le N \le 100), 편의상 1 \ldots N으로 번호가 매겨져 있습니다. i번째 소는 시간 s_i에서 t_i까지 착유가 이루어지며, 착유 과정에서 b_i개의 양동이가 필요합니다. 여러 소가 동시에 착유될 수도 있는데, 이 경우 그 소들은 동일한 양동이를 공유할 수 없습니다. 즉, 소 i에 배정된 양동이는 시간 s_i에서 t_i 사이에는 다른 어떤 소의 착유에도 사용될 수 없습니다. 물론 그 양동이는 이 시간 구간 밖에서는 다른 소에 사용할 수 있습니다. 단순화를 위해 FJ는 어떠한 순간에도 착유가 시작되거나 끝나는 소가 동시에 둘 이상 존재하지 않도록(즉, 모든 s_i와 t_i는 서로 서로 다름) 조치해 두었습니다.

FJ의 창고에는 1, 2, 3, ... 처럼 연속적으로 번호가 매겨진 양동이들이 보관되어 있습니다. 현재의 착유 전략에서는 어떤 소(예: 소 i)의 착유가 시작될 때(시간 s_i) FJ가 창고로 달려가 사용 가능한 양동이들 중에서 라벨이 가장 작은 b_i개의 양동이를 가져와 소 i에게 할당합니다.

모든 소들을 성공적으로 착유하기 위해 FJ가 창고에 보유해야 하는 양동이의 총 개수를 구하세요.


입력

입력의 첫 줄에는 정수 N이 주어집니다.
다음 N개의 줄은 각각 한 마리 소에 대한 정보를 나타내며, 각 줄에는 공백으로 구분된 정수 s_i,t_i, b_i가 순서대로 주어집니다.
s_i와 t_i는 1 \ldots 1000 범위의 정수이고, b_i는 1 \ldots 10 범위의 정수입니다. [입력 형식]


출력

한 줄에 FJ가 필요로 하는 양동이의 총 개수를 나타내는 정수 하나를 출력하세요.


예제 

3
4 10 1
8 13 3
2 6 2
4

이 예에서 FJ는 총 4개의 양동이가 필요합니다. 그는 시간 2에 시작하는 소 3의 착유에 양동이 1번과 2번을 사용합니다. 시간 4에 시작하는 소 1의 착유에는 양동이 3번을 사용합니다. 소 2가 시간 8에 도착했을 때 양동이 1번과 2번은 사용 가능하지만 3번은 아직 사용 중이므로, 그는 양동이 1번, 2번, 4번을 사용합니다.



출처

USACO 2018 December Bronze

로그인해야 코드를 작성할 수 있어요.