| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 (추가 시간 없음) | 1024 MB | 48 | 22 | 20 | 50.000% |
You are organizing the annual "Boost the Global Opulence" fundraiser concert and have received an extraordinarily amount of requests from musicians that want to perform. However, you only have one stage, so you can not invite all of them.
Each musician has a certain potential for attention, and you want to maximize the total attention potential for the concert.
But the musicians are very stubborn. They require that they can choose when their performance starts and for how long it lasts. More specifically, all of them have given you a start time and end time for their performance. If you cannot guarantee this, they will not perform at all.
The first line contains a single integer 1ドル \leq n \leq 150,000円,ドル the number of musicians. Then follows $n$ lines, one for each musician. Each line contains three space-separated integers $s,ドル $e$ and $a,ドル where 0ドル \leq s \leq 10^6$ is the start time, $s < e \leq 10^6$ is the end time, and 0ドル \leq a \leq 10^6$ is the attention potential of the musician.
Output the maximum total attention for the concert. In other words, pick a subset of the musicians to perform on the stage that maximize the sum of their attention potential, subject to the requirements that every musician gets their preferred time slot and there are no overlapping performances.
4 0 2 3 5 10 6 1 7 10 8 10 2
12
2 0 1 1 1 2 1
2
Contest > Bergen Open > Bergen Open 2021 L번