| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 0.8 초 | 1024 MB | 1 | 1 | 1 | 100.000% |
A mountain range can be represented as a broken line that starts and ends at sea level (altitude 0) and has strictly positive altitudes in between (these are called inner altitudes). Alice and Bob start climbing the mountain range from both ends. They can move along the mountain range, back and forth, but they must stay at the same altitude (between them).
The effort of a path taken by Alice is the sum of absolute differences in altitudes on the path. Specifically, if Alice’s path begins at altitude h1 = 0, changes directions at altitudes h2, h3, ..., hP-1 and ends at altitude hP, then the effort of that path is |h2−h1|+|h3−h2|+⋯+|hP−hP−1|. (It follows that Bob will make an equal effort during this time).
Find the smallest effort Alice and Bob need to make in order to meet.
The mountain range is encoded as an array of N integers containing the altitudes of the segment endpoints. The first line contains N. The second line contains the N integers. The first and last integers are guaranteed to be 0.
Print a single integer, the minimum effort required for Alice and Bob to meet. If there is no way for them to meet, print the word NO instead.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 25 | All inner altitudes are distinct. |
| 2 | 25 | N × H ≤ 40,000, where H is the highest altitude. |
| 3 | 50 | none |
5 0 4 2 7 0
11
Alice and Bob move towards one another to altitude 4. Then they both move right and descend to altitude 2. Finally, they move towards one another and meet at altitude 7.
7 0 10 1 20 5 10 0
48