Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.
First asked in IMPC14, Question by Ilir Capuni.
Cinema Millennium
Question:
Cinema Millennium in Tirana is screening the
Frozen -- a movie that recently was awarded
Oscar and was rendered by my student N. Sinno.
N (1 ≤ N ≤ 10000) people are queued
(in an appropriate queue!)
in front of the vending counter. It takes T(k)
units of time to the k-th person in this line to
buy the ticket.
However, if the k-th person and k+1-th person
buy their ticket together, they will need only
P(k) units of time, for k=1, ..., N-1, which may
be (but is not necessarily) faster (1≤ T(k),
P(k) ≤ 100). Calculate the minimal total time needed
for all of them to buy tickets.
Input specification
Number N and arrays T and P.
Output specification
Minimum time required to buy tickets
for all the people.
Sample Input
5
2 3 6 2 1
2 4 8 6
|
Sample Output
9
|
Для отправки решений необходимо выполнить вход.
|