레이팅 미적용In the heart of the Glass Valley lies a mysterious star temple, a place known for
its collection of magical crystals that shine like stars. Each crystal holds special
power and emits a radiant glow that illuminates the entire valley, as long as it
remains untouched.
The temple guardian’s nightly task is to touch ONLY the crystals located within the
specified ranges of the valley’s residents, while honoring all of their requirements.
Each resident’s request tells the guardian which range of crystals must NOT stop
shining BEFORE their bedtime, as they fear the darkness.
The guardian starts his journey at the temple entrance and must carefully coordinate their movements
to dim the crystals such that they stop shining at the correct moment. The crystals are arranged in a
line, spaced one meter apart from each other (the first crystal is one meter away from the entrance). The
guardian can move at a speed of one meter per second and may stop when needed. The time it takes for
the guardian to touch and dim a crystal is negligible. Given the residents’ requests, the temple guardian
wants to know the minimum number of seconds required to fulfill all requests (the guardian does not need
to return to the starting position).
In the first line is an integer \(N\) (\(1 \le N \le 5000\)), number of residents’ requests.
In the next N lines are integers \(l_{i}\), \(r_{i}\), \(t_{i}\) (\(1 \le l_{i} \le r_{i} \le 1e\)18, \(1 \le t_{i} \le 1e\)18), representing the left and right
bounds of the crystal range and the resident’s bedtime, respectively.
In the first and only line output the minimum time in seconds required for the guardian to fulfill all the
requests.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 20점 | \(n \le 18\), \(l_{i} = r_{i}\) for all \(i = 1\), 2, . . . , n |
2 | 25점 | \(l_{i} = 1\) for all \(i = 1\), 2, . . . , n |
3 | 55점 | \(l_{i} = r_{i}\) for all \(i = 1\), 2, . . . , n |
4 | 20점 | No additional constraints. |
3
1 1 1
3 3 5
5 5 373
1 2 1
1 1 5
1 3 463
6 6 6
8 8 7
9 9 99Clarification of the second example:
The temple guardian will first take 3 seconds to reach the 3rd crystal. Then, he will wait for 1 second and
dim the 3rd crystal. After that, he will take 1 second to go to the 2nd crystal and dim it. Finally, he will
take 1 second to reach the 1st crystal and dim it. In total, his journey will last 6 seconds, which is the
minimum time required to fulfill all the requests.