HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Contests > IMPC - 2013-2014 > problem:


14-01-50. 50795 - Trunk

IMPC - 2013-2014

Start: Mar.16.2013 at 12:00:00 PM
Finish: Mar.16.2013 at 05:00:00 PM
The contest is finished!
• Contest scoreboard

Guest
• Review clarifications (1)

Contest problems

• 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. 50468 - Draw Matrix - 2
• 14-03-80. 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.
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