ページが読み込まれませんか？ こちらをクリックすると直るかもしれません。
Placeholder

#6986
サブタスク

네 구간 1s 1024MB

問題

수열 A는 N개의 정수들로 이루어져 있다.

수열 A를 네 구간으로 나누려고 한다. (하나의 구간에는 반드시 연속된 원소만이 존재한다)

예를 들어 A=[2,4,1,3,5]이라면, [2],[4],[1],[3,5]와 같이 나누거나 [2],[4,1],[3],[5]와 같이 나누는 등 다양한 방법이 가능하다.

구간을 나누는 비용은 각 구간의 곱의 합으로 결정된다.

하나의 구간이 i에서 j까지라면, 해당 구간의 곱은 A_i × A_{i+1} × ... × A_{j-1} × A_j (i ≤ j)으로 결정되고, 각 네 구간의 곱의 합이 최종적인 비용이 된다.

비용의 최댓값과 최솟값을 구하는 프로그램을 작성하시오.


入力

첫 번째 줄에 정수 N이 주어진다. (4 \le N \le 12)

두 번째 줄에 수열 A의 원소들 A_1, A_2, ...\ ,A_N이 주어진다. (1 \le A_i \le 9)


出力

첫 줄에 비용의 최댓값을 출력한다.

다음 줄에 비용의 최솟값을 출력한다.


部分問題

番号 点数 条件
#112点

N=4

#25点

A_i = 1, (1 \le i \le N)

#331点

A_i = A_{i+1}, (1 \le i \le N-1)

#452点

추가 제한 없음


例題 #1

7
2 5 3 1 4 2 3
67
23

최댓값: (2) + (5 \times 3 \times 1 \times 4) + (2) + (3) = 67

최솟값: (2 \times 5) + (3) + (1 \times 4) + (2 \times 3) = 23


例題 #2

12
9 9 9 9 9 9 9 9 9 9 9 9
387420516
2916


出典

klee
ログインしないとコードを書けません。