Xếp hàng mua vé

Points: 0.05 (partial)

Time limit: 1.0s

Memory limit: 256M

Input: stdin

Output: stdout

Problem source:

VNOI Marathon '08 - Practice Round

Problem type

Allowed languages

C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Có ~N~ người sắp hàng mua vé dự buổi hoà nhạc. Ta đánh số họ từ ~1~ đến ~N~ theo thứ tự đứng trong hàng. Mỗi người cần mua một vé, song người bán vé được phép bán cho mỗi người tối đa hai vé. Vì thế, một số người có thể rời hàng và nhờ người đứng trước mình mua hộ vé. Biết ~t_{i}~ là thời gian cần thiết để người ~i~ mua xong vé cho mình. Nếu người ~i+1~ rời khỏi hàng và nhờ người ~i~ mua hộ vé thì thời gian để người thứ ~i~ mua được vé cho cả hai người là ~r_{i}~.

Yêu cầu: Xác định xem những người nào cần rời khỏi hàng và nhờ người đứng trước mua hộ vé để tổng thời gian phục vụ bán vé là nhỏ nhất.

Input

Dòng đầu tiên chứa số ~N~ ~(1 \leq N \leq 60000)~.
Dòng thứ hai ghi ~N~ số nguyên dương ~t_{1}~, ~t_{2}~, ..., ~t_{N}~. ~(1 \leq t_{i} \leq 30000)~
Dòng thứ ba ghi ~N-1~ số nguyên dương ~r_{1}~, ~r_{2}~, ..., ~r_{N-1}~. ~(1 \leq r_{i} \leq 30000)~

Output

In ra tổng thời gian phục vụ nhỏ nhất.

Sample Input

5
2 5 7 8 4
4 9 10 10

Sample Output

Comments

Please read the guidelines before commenting.

-4

khiemgia1105 commented on Oct. 4, 2024, 7:48 a.m.

Mn đăng kí khoắ học ở prf mình nhé, cam kết có giải

-7

This comment is hidden due to too much negative feedback. Show it anyway.

-4

MalazeKL commented on July 2, 2024, 6:04 p.m. ← edit 6 →

.

-5

MalazeKL commented on July 2, 2024, 6:05 p.m. ← edited →

.

This comment is hidden due to too much negative feedback. Show it anyway.

-13

hieuz08 commented on June 11, 2024, 2:12 a.m.

ĐỊt mẹ thg Minh Hiếu 3==Đ

This comment is hidden due to too much negative feedback. Show it anyway.

1

nhanphamj commented on July 27, 2024, 2:24 p.m.

ko chửi bạn

-12

This comment is hidden due to too much negative feedback. Show it anyway.

-6

thanhhoang commented on Jan. 23, 2024, 7:01 p.m.

Quy Hoạch Động f[n] = t[n]; f[i] = min( t[i] + f[i + 1], r[i] + f[i + 2] ) ( i : n - 1 --> 1 )

This comment is hidden due to too much negative feedback. Show it anyway.

-4

thanhhoang commented on Jan. 23, 2024, 7:02 p.m.

=> f[1]

-15

Cuunon311 commented on Oct. 8, 2023, 4:14 a.m.

uk

This comment is hidden due to too much negative feedback. Show it anyway.

-32

kevininyourarea commented on April 14, 2023, 1:46 a.m.

để cmt ở đây để xin upvote :>

This comment is hidden due to too much negative feedback. Show it anyway.

-31

NguyenDongAnh commented on Sept. 9, 2022, 2:29 p.m. ← edited →

Bài Hay nhỉ

This comment is hidden due to too much negative feedback. Show it anyway.

23

sickboy1368 commented on Jan. 11, 2022, 6:46 a.m.

quy hoạch động so sánh ( f[i-1] + t[i] ) với ( f[i-2] + r[i-1] )

-51

nictysine1 commented on Feb. 16, 2022, 8:41 a.m. ← edited →

upvote

This comment is hidden due to too much negative feedback. Show it anyway.

-351

ltphuc commented on April 20, 2021, 3:45 a.m.

Em la newbie moi bat dau hoc tin, ai co the cho em xin code voi a, em cam on moi nguoi nhieu

This comment is hidden due to too much negative feedback. Show it anyway.

-138

nngovannhhungg commented on Jan. 15, 2022, 7:19 a.m.

cần thêm 2 người downvote nx cho chẵn :))

This comment is hidden due to too much negative feedback. Show it anyway.

-150

manhtuan22007 commented on Nov. 27, 2021, 12:54 p.m.

cần thêm 1 người downvote nx cho chẵn :))

This comment is hidden due to too much negative feedback. Show it anyway.

-147

ekhoavvdd commented on Nov. 22, 2021, 4:31 p.m.

cần thêm 1 người downvote nữa cho chẵn :))

This comment is hidden due to too much negative feedback. Show it anyway.