HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Volumes > Data Structures > problem:


50676 - Cinema Millennium

Guest
• Review clarifications (2)

Volume problems

• 50367 - Bar Codes
• 50386 - Conformity
• 50711 - Snail Trails
• 50472 - Minimum Sum Triangle
• 50842 - Minimum Sum Triangle - DP
• 50549 - k-Nearest Neighbours (kNN)
• 50676 - Cinema Millennium
• 50678 - The Jumping Rabbit
• 50306 - Beautiful Numbers
• 50700 - Candidates for the Mayor
• 50692 - How much money?
• 50790 - Fire Alarm
• 50710 - Permutations
• 50709 - k-ary Strings
• 50708 - Binary Strings

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