Problem
핸썸 잭은 자신만의 이리듐 처리 공장을 세우고 싶어합니다.
Jack이 관리하는 n개의 공장이 있으며 각 공장은 1부터 n까지 번호가 매겨져 있습니다. 각 공장은 이리듐 광상에 위치하며, 이곳에서도 함께 채굴됩니다. 그리고 공장 번호가 높을수록 최신 제품입니다.
각 플랜트에는 효율성 지수 a
i가 있습니다. 양수, 음수 또는 0일 수 있습니다.
각 공장은 이리듐 광석을 처리해야 합니다. 자신의 광상을 사용하거나 과거에 다른 공장에서 처리한 광석을 파이프라인을 통해 가져올 수 있습니다. 그러나 이 과정은 다소 제한적입니다. 첫째, 파이프라인 시스템에 과부하가 걸리지 않도록 하기 위해 각 플랜트는 추가 처리를 위해 서로 엄격하게 광석을 수용할 수 있습니다(또는 자체 매장량을 수용하고 사용하지 않음). 둘째, 오래된 공장은 기술적으로 새로운 공장 이후 광석을 재처리할 수 없습니다.
전체 시스템의 최종 성능은 다음과 같이 계산됩니다. 각 플랜트에 대해 효율성 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 * 1 = 1이다. 2공장은 2차 가공을 하고 생산성은 5 * 2 = 10이다. 그리고 3공장은 받은 광석을 3차 가공하므로 생산성은 3 * 3 = 9입니다. 총 성능은 1 + 10 + 9 = 20입니다.
이 예에서 두 번째와 세 번째 플랜트는 교체할 수 없습니다. 두 번째 공장은 세 번째보다 오래되었기 때문에 기술적인 이유로 세 번째 이후에 광석을 처리할 수 없습니다.
두 번째 예에서 첫 번째와 세 번째 공장은 광상을 사용하고 두 번째 공장은 첫 번째 공장에서 광석을 받습니다.