← 返回题目列表

AtCoder · joisc2022_b

B. 京都观光

中文机器翻译题面 查看原题

以下是来自日本的官方新闻原版PDF,已经完整保存和染色。

京都観光 (Sightseeing in Kyoto) - 原题 PDF 第 1 页
原题PDF第1页
京都観光 (Sightseeing in Kyoto) - 原题 PDF 第 2 页
原题PDF第2页
京都観光 (Sightseeing in Kyoto) - 原题 PDF 第 3 页
原题PDF第3页
可复制的 PDF 提取文本
The 21st Japanese Olympiad in Informatics (JOI 2021/2022)

                                                         Spring Training Camp/Qualifying Trial

                                                  March 20–23, 2022 (Komaba, Tokyo)


                                                                 Contest 1 – Sightseeing in Kyoto

               京都観光(Sightseeing in Kyoto)




 京都市は世界的な観光地であるとともに,格子状の道路でも有名である.あなたは京都市に観光に来てお

り,できるだけ早く目的の観光名所まで歩いて移動したいと思っている.ここで,現実を単純化した次のよ

うな状況設定を考えたい.

 この都市には,東西に伸びる道路がH 本,南北に伸びる道路がW 本通っており,これらは都市全体を

(H −1) × (W −1) 個の正方形の区画に分ける碁盤の目のような形をなしている.北からi 本目(1 ≦i ≦H)

の東西方向の道路と,西からj 本目(1 ≦j ≦W) の南北方向の道路が交わる場所を,交差点(i, j) とする.

 道路によって,広さ,材質,人通りの多さなどが様々であるため,あなたの歩く速さはすべての道路で同

じとは限らない.具体的には,各道路に対して,歩く速さは以下のようになっている.

    • 北からi 本目(1 ≦i ≦H) の東西方向の道路を1 区画分歩くのにはAi 秒かかる.すなわち,各c
       (1 ≦c ≦W −1) に対して,交差点(i, c) と交差点(i, c + 1) の間をAi 秒で移動できる.
    • 西からj 本目(1 ≦j ≦W) の南北方向の道路を1 区画分歩くのにはBj 秒かかる.すなわち,各r
       (1 ≦r ≦H −1) に対して,交差点(r, j) と交差点(r + 1, j) の間をBj 秒で移動できる.

ただし,あなたは京都市の美しい景観を損なうべきではないため,道路以外の部分を歩くことはできない.

 あなたは現在交差点(1, 1) におり,交差点(H, W) まで徒歩で移動したい.ただし,歩く距離が長いと疲

れるので,遠回りをせずに,すなわち一度も北方向または西方向に進まずに移動するつもりである.この条

件のもとで,できるだけ早く目的地に到着したい.

 道路の情報が与えられるので,交差点(1, 1) から交差点(H, W) まで遠回りせずに徒歩で移動するのに必

要な最短の時間を求めるプログラムを作成せよ.


入力


 入力は以下の形式で標準入力から与えられる.入力される値はすべて整数である.


    H W

      A1 A2 · · · AH
      B1 B2 · · · BW


出力

 標準出力に,交差点(1, 1) から交差点(H, W) まで遠回りせずに徒歩で移動するのに必要な最短の時間を

秒単位で表す整数を1 行で出力せよ.




                       京都観光– 1 / 3

The 21st Japanese Olympiad in Informatics (JOI 2021/2022)

                                                         Spring Training Camp/Qualifying Trial

                                                  March 20–23, 2022 (Komaba, Tokyo)


                                                                 Contest 1 – Sightseeing in Kyoto



制約

    • 2 ≦H ≦100 000.

    • 2 ≦W ≦100 000.
    • 1 ≦Ai ≦1 000 000 000 (= 109) (1 ≦i ≦H).
    • 1 ≦Bj ≦1 000 000 000 (= 109) (1 ≦j ≦W).


小課題

    1. (10 点) H ≦1 000,W ≦1 000.
    2. (30 点) Ai ≦1 000 (1 ≦i ≦H),Bj ≦1 000 (1 ≦j ≦W).
    3. (60 点) 追加の制約はない.


入出力例

  入力例1              出力例1

   2 2                            5

   1 3

   2 5

 交差点(1, 1) から交差点(2, 2) まで遠回りせずに徒歩で移動する方法には,以下の2 通りがある.

    • 交差点(1, 1) →(1, 2) →(2, 2) の経路で移動する.これにはA1 + B2 = 1 + 5 = 6 秒かかる.
    • 交差点(1, 1) →(2, 1) →(2, 2) の経路で移動する.これにはB1 + A2 = 2 + 3 = 5 秒かかる.

 そのため,移動にかかる最短の時間は5 秒である.よって5 を出力する.なお,2 つの移動経路を図で表

すと以下のようになる.ここで,図中の各道路に対応する整数は,その道路を1 区画分歩くのにかかる時間

を表している.





                       京都観光– 2 / 3

The 21st Japanese Olympiad in Informatics (JOI 2021/2022)

                                                         Spring Training Camp/Qualifying Trial

                                                  March 20–23, 2022 (Komaba, Tokyo)


                                                                 Contest 1 – Sightseeing in Kyoto



 この入力例はすべての小課題の制約を満たす.


  入力例2              出力例2

   5 5                            20

   7 1 5 2 8

   7 2 4 1 6

 例えば,下図のような経路で移動すると,交差点(1, 1) から交差点(5, 5) まで20 秒で移動できる.移動時

間を19 秒以内にする方法は存在しないため,20 を出力する.なお,図中の各道路に対応する整数は,その

道路を1 区画分歩くのにかかる時間を表している.





 この入力例はすべての小課題の制約を満たす.


  入力例3                               出力例3

   4 6                                                        2737473954

   454863204 543362989 866044086 813602010

   71574269 17945210 688720933 392135202 38174709 168241720

 この入力例は小課題1, 3 の制約を満たす.





                       京都観光– 3 / 3