ГлавнаяСборникиТурнирыРазделыФорумыУчастникиПечатьПомощьО системе

Турниры > IMPC - 2013-2014 > задача:


14-01-50. 50795 - Trunk

IMPC - 2013-2014

Старт: 16.мар.2013 в 12:00:00
Финиш: 16.мар.2013 в 17:00:00
Турнир завершён!
• Турнирная таблица

Гость
• Вопросы к жюри (1)

Задачи турнира

• 50386 - Conformity
• 14-01-10. 50457 - The Number of W...
• 14-01-40. 50419 - The longest bitoni...
• 14-01-50. 50795 - Trunk
• 14-03-10. 50412 - K numbers
• 14-03-20. 50398 - Sum of kth Anti-d...
• 14-03-30. 50377 - kth Permutation
• 14-03-40. 50773 - Balanced Sum Tree
• 14-03-60. 50382 - Parkside's Other ...
• 14-03-70. 50468 - Draw Matrix - 2
• 14-03-70. s
• 14-03-80. 50675 - Kruja Boys

Обратная связь

Если у вас есть предложения или пожелания по работе Contester, посетите форум сайта www.contester.ru.

Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
Question by Osman Ay.

Trunk

The wood company Moon-Wood is dealing with the business of cutting down the old trees in the Alpine forest and selling them. The company used to carry the trunks to the factory via rivers and cut them into smaller pieces in the factory. However, the company has some difficulty in carrying the big trunks to the factory due to the decrease in the water level. In order to solve this problem the company decided to cut trunks into pieces, in the forest, and float the pieces to the factory.

Cutting a trunk into two pieces has a cost, which is equal to the length of the trunk. Make a program to calculate the minimum cost of cutting a trunk with the length L into the N smaller pieces with the lengths of L1, L2… Ln. At a time, you can cut a trunk only into two pieces.

Input specification
The input consists of two lines. In the first line, there are two integers: L and N, where L denotes the length of the trunk and N denotes the number of the pieces and 1 ≤ L ≤ 100.000; 1 ≤ N ≤ 40.000. In the second line, there are N positive integers separated with a space representing the lengths of the pieces. The sum of the numbers in the second line is always equal to L.

Output specification
Output contains an integer that is the minimum cost of cutting the given trunk into the given smaller pieces.

 Sample Input I   
  10 5
  1 3 2 1 3
 Sample Input II   
  20 6
  2 4 4 8 1 1
 Sample Output I   
  22
 Sample Output II   
  46


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

www.contester.ru