<ПРЕД Задача:
СЛЕД>
Задачу решили 1147 пользователей: ...
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

CD

Time limit = 5 секунд(ы)

Memory limit = 33000 Kb

Вам предстоит длительная поездка на автомобиле. У вас есть магнитофон, но, к сожалению, ваша любимая музыка вся на CD-дисках. Вам надо переписать её на кассеты, а для этого надо решить следующую задачу. У вас есть кассета вместимостью N минут. Как выбрать композиции с CD-диска, чтобы на кассете осталось как можно меньше свободного места?

Предположения:

Вход Значение N, число композиций и их длительности. Для первого примера входных данных имеем: N=5, число композиций=3, первая композиция длится 1 минуту, вторая — 3 минуты, следующая — 4 минуты.

Выход Максимальная сумма длительностей звучания.

Вход#1
5 3 
1 3 4
Выход#1
5

Вход#2
10 4
9 8 4 2

Выход#2
10

Вход#3
20 4 
10 5 7 4

Выход#3
19

Вход#4
90 8
10 23 1 2 3 4 5 7

Выход#4
55

Вход#5
45 8
4 10 44 43 12 9 8 2

Выход#5
45

Автор:

<ПРЕД | Вернуться к списку задач | Искать сообщения в форуме | СЛЕД>


© acm.mipt DevGroup
The page was generated in 180ms

SW soft NIX
ID = 107.23.129.77