Casino
Дизайн и Анализ на Алгоритми, 2011
Time Limit: 0.2s, Memory Limit: 64MiB
След като взе първата заплата от стажа си, Ели реши да инвестира парите в нещо сигурно и доходоносно – а именно, хазарт. Тя беше чула, че в едно от новите казина има интересна игра със следните правила:
В началото играчът започва със сума нула и маса с N пула със стойности A1, A2, …, AN. На всеки ход играчът има право да:
В началото играчът започва със сума нула и маса с N пула със стойности A1, A2, …, AN. На всеки ход играчът има право да:
- Вземе произволен пул, да прибави към сумата си стойността му и да го махне от масата. или
- Вземе произволни два пула, да прибави произведението на стойностите им към сумата си и да ги премахне от масата.
Вход
На първия ред на стандартния вход ще бъде зададен броят пулове N, а на следващия ще има N цели числа A1, A2, ..., AN – стойностите на всеки пул.
Изход
На единствен ред на стандартния изход изведете максималната сума, която може да бъде постигната при оптимална игра.
Ограничения
- 1 ≤ N ≤ 1,000
- -1,000 ≤ Ai ≤ 1,000
Примерен Вход | Примерен Изход |
---|---|
3 -16 0 42 | 42 |
7 0 2 -1 2 7 -3 -4 | 28 |
В първия тест единственото решение е да вземем 42 + (-16 * 0) и да получим 42. Едно от решенията на втория тест е да се вземат (-3, -4), (0, -1), (2), (2 * 7), даващо 12 + 0 + 2 + 14 = 28.