P9521 [JOIST 2022] Sightseeing in Kyoto / Sightseeing in Kyoto

JOISC2022 D1T2

Kyoto is a world-famous sightseeing city, and it is also known as a grid city. You come to Kyoto for sightseeing, and you plan to visit a famous attraction on foot. In this problem, we consider the following simplified setting. In the city, there are $H$ east-west streets and $W$ north-south streets, so the city forms an $(H-1)\times(W-1)$ grid. The intersection of the $i$-th street from the north and the $j$-th street from the west is called intersection $(i,j)$. Different streets may have different materials, widths, and crowd levels, so your walking speed may differ. For each street, your walking time is as follows: - If you walk one unit length along the $i$-th street from the north, it takes $A_i$ seconds. That is, walking from intersection $(i,c)~\left(i\in[1,H],c\in[1,W)\right)$ to intersection $(i,c+1)$ takes $A_i$ seconds. - If you walk one unit length along the $j$-th street from the west, it takes $B_j$ seconds. That is, walking from intersection $(c,j)~\left(c\in[1,H),j\in[1,W]\right)$ to intersection $(c+1,j)$ takes $B_j$ seconds. You are currently at intersection $(1,1)$ and want to go to $(H,W)$. You must walk along the streets, and you do not want to take detours, meaning you will not move north or west. You want to arrive as early as possible. Please compute the minimum time needed to travel from intersection $(1,1)$ to intersection $(H,W)$ under the given conditions.

The first line contains two integers $H,W$, representing the numbers of streets. The second line contains $H$ integers, where the $i$-th integer $A_i$ represents the walking time on the $i$-th east-west street from the north. The third line contains $W$ integers, where the $i$-th integer $B_i$ represents the walking time on the $i$-th north-south street from the west.

Output one integer in one line, representing the minimum walking time required.

**Sample Explanation #1** There are two routes from $(1,1)$ to $(2,2)$: 1. $(1,1)\rightarrow(1,2)\rightarrow(2,2)$, which takes $1+5=6$ seconds. 2. $(1,1)\rightarrow(2,1)\rightarrow(2,2)$, which takes $2+3=5$ seconds. Therefore, the minimum time is $5$ seconds. This sample satisfies the constraints of all subtasks. **Sample Explanation #2** The optimal route is shown in the figure below:  This sample satisfies the constraints of all subtasks. **Sample Explanation #3** This sample satisfies the constraints of subtasks $1,3$. **Constraints** For all testdata: - $2\leq H,W\leq 100000$. - $1\leq A_i\leq 10^9$ $(i\in[1,H])$. - $1\leq B_i\leq 10^9$ $(i\in[1,W])$. The additional constraints and scores for subtasks are as follows: |Subtask ID|Additional Constraints|Score| |:-:|:-:|:-:| |$1$|$H,W\leq 1000$|$10$| |$2$|$A_i\leq 1000, B_i\leq 1000$|$30$| |$3$|No additional constraints.|$60$| Translated by ChatGPT 5