시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 74 | 59 | 54 | 80.597% |
Just Oishi Ichigo 農園 (以下 JOI 農園) は東西に細長いことで有名ないちご農園であり,その入り口は農園の最も西にある.以下では,入り口から東に k メートル進んだ場所を地点 k と呼ぶことにする.
JOI 農園内には N 個のいちごがなっている.それぞれ 1 から N の番号がつけられている.どのいちごも時刻 0 までは青い.いちご i (1 ≦ i ≦ N) は地点 Ai に実をつけており,時刻 Ti になると熟し赤い状態になる.
いちごは青い状態では収穫できない.つまり,いちご i は時刻 Ti となるまで収穫できない.あなたは時刻 0 に地点 0 にある農園の入り口から出発して,最大秒速 1 メートルで東西方向に移動しながらいちごを収穫する.いちごを収穫するのにかかる時間は無視できるとする.
いちご農園についての情報が与えられるので,すべてのいちごを赤い状態で収穫したあと入り口に帰ってくるまでにかかる時間の最小値を求めるプログラムを作成せよ.
入力は以下の形式で標準入力から与えられる.
N A1 T1 A2 T2 : AN TN
すべてのいちごを赤い状態で収穫したあと入り口に帰ってくるまでにかかる時間の最小値を 1 行に出力せよ.
10 1 3 2 1 3 4 4 1 5 5 6 9 7 2 8 6 9 5 10 3
20
はじめの 10 秒かけて地点 10 まで移動すると,その道中でいちご 2, 4, 5, 7, 8, 9, 10 をこの順に収穫することができる.その後 10 秒かけて地点 0 まで戻ると,その道中でいちご 6, 3, 1 をこの順に収穫することができる.これで 10 個すべてのいちごを赤い状態で収穫することができる.
10 0 450 5 445 10 430 15 405 20 370 25 325 30 270 35 205 40 130 45 45
450
以下のように移動すると 450 秒ですべてのいちごを赤い状態で収穫できる.
15 11 23 3 94 89 3 38 58 65 29 41 3 80 42 22 76 48 85 83 98 87 29 97 96 22 75 57 25 99 33
198