시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 1024 MB | 46 | 34 | 30 | 85.714% |
Kyoto City is a worldwide sightseeing place. It is also known as a city with grid of streets. You are now visiting Kyoto City for sightseeing. You are planning to visit a famous spot on foot. You want to arrive there as early as possible. In this task, we consider the following simplified situation.
In this city, there are $H$ streets in the east-west direction, and $W$ streets in the south-north direction. The shape of the city is a grid of $(H - 1) \times (W - 1)$ cells. The crossing of the $i$-th street ($1 ≤ i ≤ H$) from the north and the $j$-th street ($1 ≤ j ≤ W$) from the west is denoted by $(i, j)$.
Different streets may have different width, material, and crowdedness. Your walking speed may be different for different streets. For each street, your walking speed is determined as follows.
In order not to destroy the beautiful landscape of Kyoto City, you are not allowed to walk outside the streets.
Now you are in the crossing $(1, 1)$. You want to walk to the crossing $(H, W)$. Since you will be tired if you walk for long distance, you do not want to make a detour. You will not walk to the north or west direction. Under this condition, you want to arrive at the destination as early as possible.
Write a program which, given information of the streets, calculates the minimum time to walk from the crossing $(1, 1)$ to the crossing $(H, W)$ without making a detour
Read the following data from the standard input. Given values are all integers.
$\begin{align*} & H \, W \\ & A_1 \, A_2 \, \cdots \, A_H \\ & B_1 \, B_2 \, \cdots \, B_W \end{align*}$
Write one line to the standard output. The output should contain the minimum time (seconds) to walk from the crossing $(1, 1)$ to the crossing $(H, W)$ without making a detour.
번호 | 배점 | 제한 |
---|---|---|
1 | 10 | $H ≤ 1\,000$, $W ≤ 1\,000$. |
2 | 30 | $A_i ≤ 1\,000$ ($1 ≤ i ≤ H$), $B_j ≤ 1\,000$ ($1 ≤ j ≤ W$). |
3 | 60 | No additional constraints. |
2 2 1 3 2 5
5
There are two ways to walk from the crossing $(1, 1)$ to the crossing $(2, 2)$ without making a detour.
Since the minimum time is $5$ seconds, output $5$. These two ways are described in the following figure. An integer in the figure is the time needed to walk for the unit length on the corresponding street.
This sample input satisfies the constraints of all the subtasks.
5 5 7 1 5 2 8 7 2 4 1 6
20
For example, if you walk from the crossing $(1, 1)$ to the crossing $(5, 5)$ in the following way, it takes $20$ seconds. Since it is impossible to walk in $19$ seconds or less, output $20$. An integer in the figure is the time needed to walk for the unit length on the corresponding street.
This sample input satisfies the constraints of all the subtasks.
4 6 454863204 543362989 866044086 813602010 71574269 17945210 688720933 392135202 38174709 168241720
2737473954
This sample input satisfies the constraints of Subtasks 1, 3.