지구 온난화와 환경 위기로 인해 자연 재해에 대비해 생존 계획을 세워야 한다. 이번에는 쓰나미에 대한 대피 매뉴얼을 만들어 보자.

바다선은 x축과 평행한 직선 y=k로 나타낼 수 있다. 보통 k는 0이지만, 쓰나미가 발생하면 양의 실수가 된다.

도시에는 점 (p_i,q_i)로 표시된 N개의 대피 장소가 있다. 이 장소들에서는 동시에 모이고 움직인다. 또한 각 장소에는 r_i가 주어지는데, 이는 그 장소로 가는데 걸리는 시간(분 단위)을 의미한다.

대피에 방해가 되는 장애물이 있다. 단순화를 위해 장애물은 x축과 평행한 직선이라고 가정한다.

총 M개의 장애물이 (s_i,e_i,y_i,t_i)로 주어지는데, 이는 점 (s_i,y_i)와 (e_i,y_i)를 잇는 선분으로, 이를 횡단하는데 t_i분이 걸린다는 것을 의미한다. 끝점에서도 t_i분이 걸린다는 것에 주의하라. 장애물과 대피 장소는 겹치지 않는다.

하지만 장애물끼리는 겹칠 수 있다. 이 경우, 겹친 장애물을 횡단하는 시간은 겹친 t_i들의 합이 된다. 예를 들어, 장애물이 (1,4,2,5)와 (3,5,2,7)이라면, x=1에서 횡단하는데 5분, x=3에서 횡단하는데 5+7=12분, x=5에서 횡단하는데 7분이 걸린다.

우리는 y=Y에 도달할 때까지 위쪽(즉, +y 방향)으로만 움직인다. 위쪽으로 움직이면서 x좌표도 바꿀 수 있다. 현재 y좌표가 i와 i+1 사이일 때 x축을 따라 한 좌표 이동하는데 c_i분이 걸린다. 예를 들어 c_3=5이고 y=3.5일 때 x좌표를 10에서 6으로 바꾸면 5×∣10−6∣=20분이 걸린다.

우리는 정수 x좌표로만 움직일 수 있으며, 정수 y좌표에서는 x좌표를 바꾸지 않는다. 이것이 유일한 제약사항이다. 원한다면 x=−100이나 x=10^{100}으로도 움직일 수 있다.

또한 c_1,...,c_{Y−1}은 증가하는 수열이라는 것에 주의하라. y가 증가함에 따라 사람 수도 증가하기 때문에, 사이를 움직이기가 어려워지기 때문이다.

대피 매뉴얼은 다음과 같다:

1. 적절한 대피 장소로 이동한다.
2. 그 장소에서 시작하여 주어진 제약 조건 하에 y=Y로 이동한다. 우리는 단순히 위쪽으로 움직이는 시간은 고려하지 않는다. 왜냐하면 우리가 시작하는 대피 장소에 관계없이 거의 일정하기 때문이다. 우리는 대피 장소로 이동하는 시간, 수평으로 움직이는 시간, 장애물을 횡단하는 시간만 고려한다.

(1,Y), (2,Y), …, (X,Y)로 대피하는데 걸리는 최소 시간(분 단위)을 각각 계산해 보자.

#6125 upload 10 done 1 how_to_reg 1

쓰나미 timer 5s memory 1024MB

#6125

쓰나미 5s 1024MB