HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Sections > Dynamic programming & Greedy > problem:


50676 - Cinema Millennium

Guest
• Review clarifications (2)

Section problems

• 50672 - Math and Soldiers
• 50671 - Phalanx
• 50842 - Minimum Sum Triangle - DP
• 50676 - Cinema Millennium
• 50678 - The Jumping Rabbit
• 51149 - One Piece Arena
• 50485 - Center of gravity of a plate
• 50674 - Collecting Eggs
• 50677 - The Cottage
• 50675 - Kruja Boys
• 50679 - Jetpack Hurdle Jumping
• 50673 - DNA Testing

Feedback

If you notice incorrect translations in Contester, please let author know.

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


Для отправки решений необходимо выполнить вход.

www.contester.ru