Задача
Красавчик Джек хочет организовать свои заводы по переработке эридия.
Всего в подчинении Джека n заводов, каждый из них пронумерован от 1 до n. Каждый завод находится на месторождении эридия, где он по совместительству и добывается. И чем больше номер завода, тем он более новый.
У каждого завода есть его показатель эффективности a
i. Он может быть положительным, отрицательным или нулевым.
Каждый завод должен перерабатывать руду эридия. Можно использовать собственное месторождение либо принимать руду, в прошлом переработанную другим заводом, по трубопроводу. Однако такой процесс несколько ограничен. Во-первых, чтобы не перегружать трубопроводную систему, каждый завод может принимать руду на дальнейшую переработку строго от одного другого (либо не принимать и использовать свое месторождение). Во-вторых, более старые заводы технически не приспособлены к тому, чтобы повторно перерабатывать руду вслед за более новым заводом.
Итоговая производительность всей системы считается следующим образом: для каждого завода берется его эффективность a
i и умножается на этап переработки, который считается, как номер того, в какой раз обрабатывается поступившая руда (подробнее в пояснениям к примерам), далее все полученные значения суммируются по всем заводам.
Помогите Красавчику Джеку организовать систему так, чтобы итоговая производительность всей системы была максимально возможной.
Входные данные:
В первой строке дано натуральное число n (1 <= n <= 7) - количество заводов.
Во второй строке через пробелы даны n целых чисел, где i-ое число это a
i (-1000 <= a
i <= 1000) - базовая эффективность завода под номером i.
Выходные данные:
Выведите одно число - максимально возможную итоговую производительность всей системы.
Примеры:
| Входные данные |
Выходное данные |
3
1 5 3 |
20 |
3
1 5 -3 |
8 |
Пояснения:
В первом примере выгоднее всего чтобы первый завод добывал собственную руду, второй завод принимал руду от первого и третий принимал от второго. В таком случае первый завод выполняет первичную переработку и его производительность равна 1 * 1 = 1. Второй завод выполняет вторичную переработку, его производительность равно 5 * 2 = 10. И третий завод перерабатывает получаемую руду в третий раз, поэтому его производительность равно 3 * 3 = 9. Итоговая проиводительность равна 1 + 10 + 9 = 20.
Обратите внимание, что в данном примере второй и третий завод не могут поменяться местами, т.к. второй завод не сможет перерабатывать руду после третьего по техническим причинам, ведь он более старый, чем третий.
Во втором примере первый и третий заводы будут использовать свои месторождения, а второй завод примет руду от первого.