시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 | 512 MB | 4 | 1 | 1 | 25.000% |
高橋君は苹果(りんご)ちゃんとニューヨークを観光することになりました。 高橋君は観光するところに特に希望はなかったのですが、苹果ちゃんの熱烈な誘いにより、以下の地図にあるような"ほそながいところ"を観光することに決まりました。
Google マップ - (C)2012 Google
この"ほそながいところ"はとても細長く、直線とみなすことができます。また、"ほそながいところ"には片方の端にスタート地点が、もう片方の端にゴール地点があり、スタート地点からゴール地点へ向けて何台かの観光用の馬車が走っています。この馬車は以下のようなルールに従って運行されています。
また、先述した"ほそながいところ"と"すこしひろいところ"について、以下の制約を満たします。
これを聞いた高橋君は、以上に述べた馬車運行のルールを守りつつ馬車の出発時刻を調整することにより、1台目の馬車が発車してからすべての馬車が到着するまでにかかる時間を小さくできることを見抜きました。 高橋君の出した結果を知るために、 馬車の台数n , それぞれの馬車の速度に関するパラメータSi,"ほそながいところ"上に存在する"すこしひろいところ"の総数m ,それぞれの"すこしひろいところ"のスタート地点からの距離Di が与えられるので、 1台目の馬車が発車してからすべての馬車が到着するまでにかかる時間の最小値を求めるプログラムを書くことがあなたの仕事です。 なお、苹果ちゃんは"ほそながいところ"での観光を存分に楽しみましたが、高橋君はこの観光の後には「ほそながかった…」としかつぶやかなかったそうです。
入力形式は以下のようになっている。
dist n S1 S2 .. Sn m D1 D2 .. Dm
1台目の馬車が発車してからすべての馬車が到着するまでにかかる時間の最小値を1行に出力せよ。単位は分である。
100 2 1 2 0
201
2台目は1台目が出発した1分後に出発する。
100 2 2 1 0
200
2台目は1台目が出発した100分後に出発し、ゴールで1台目に追いつく。
100 3 2 1 1 1 50
200
2台目は1台目が出発した50分後に出発し、50mのひろいところで1台目を抜く。
3台目は1台目が出発した100分後に出発し、ゴールで1台目に追いつく。
100 4 3 1 1 3 2 40 60
421