라이브 에이드

면접 대비

시간 제한3초메모리 제한1024 MB

요약

각 연주자의 시작 시각, 종료 시각, 주목도가 주어질 때 겹치지 않게 연주자를 골라 주목도 합의 최댓값을 구한다.

난이도: 보통10점 중 5점
유형: 동적 계획법, 정렬, 이분 탐색, 구간
정답자: 아직 제출이 없습니다

문제

당신은 연례 "지구적 부의 증대" 자선 콘서트를 준비하고 있으며, 공연하고 싶어 하는 음악가들로부터 엄청나게 많은 요청을 받았다. 그러나 무대는 하나뿐이므로 모든 음악가를 초대할 수는 없다.

각 음악가에게는 특정한 관심 잠재력이 있으며, 당신은 콘서트의 총 관심 잠재력을 최대화하려 한다.

하지만 음악가들은 매우 고집스럽다. 그들은 자신이 공연을 언제 시작하고 얼마나 오래 할지 스스로 정하겠다고 요구한다. 더 구체적으로, 모든 음악가가 공연의 시작 시각과 종료 시각을 제시했다. 이를 보장할 수 없다면, 그들은 아예 공연하지 않겠다고 한다.

입력

첫째 줄에 음악가의 수를 나타내는 정수 $1 \leq n \leq 150\,000$ 이 주어진다. 이어서 각 음악가에 대한 $n$ 개의 줄이 주어진다. 각 줄에는 공백으로 구분된 세 정수 $s$ , $e$ , $a$ 가 주어지며, 여기서 $0 \leq s \leq 10^6$ 은 시작 시각, $s < e \leq 10^6$ 은 종료 시각, $0 \leq a \leq 10^6$ 은 음악가의 관심 잠재력이다.

출력

콘서트의 최대 총 관심도를 출력한다. 다시 말해, 모든 음악가가 원하는 시간대를 배정받고 공연이 겹치지 않는다는 조건 아래에서, 관심 잠재력의 합이 최대가 되도록 무대에 설 음악가들의 부분집합을 고른다.

예제2

예제 1
입력
```
4
0 2 3
5 10 6
1 7 10
8 10 2
```
예상 출력
```
12
```
예제 2
입력
```
2
0 1 1
1 2 1
```
예상 출력
```
2
```