HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Sections > Dynamic programming & Greedy > problem:


50676 - Cinema Millennium

Guest
• Review clarifications (2)

Section problems

• 50686 - The Container
• 50524 - Elevator
• 50536 - Epoka Furgon Shpk
• 50682 - Hotel Durres
• 50526 - Gold Market
• 50930 - Tom and Jerry
• 50488 - Connecting Wires
• 50842 - Minimum Sum Triangle - DP
• 50676 - Cinema Millennium
• 50678 - The Jumping Rabbit
• 50598 - Minimum Sum
• 50683 - Parking Buses
• 50685 - Guest Room Usage
• 50674 - Collecting Eggs
• 50561 - Lucky tickets
• 50545 - Diet
• 50675 - Kruja Boys

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