No.505 カードの数式2

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 93
作問者 : kzyKTkzyKT / テスター : ixmelixmel

4 ProblemId : 1342 / 出題時の順位表

問題文

$-9 \ $~$ \ 9$の整数が書かれた$N$枚のカードが横に一列に並んでいる。
$+,-,×,÷$の書かれたカードを各整数のカードの間に$1$枚ずつ並べて数式を作りたい。(各カードは無限にある)
各演算子に優先順位はなく、左から順番に計算する。
できる数式の答えの最大値を求めよ。

【$÷$の扱い】
・0で割ることはできないので、0の前に並べてはいけない
・割り切れない場合、小数点以下は0方向に切り捨てる(無視する)

入力

$N$
$a_1 \ a_2 \ ... \ a_N$

$1$行目に$N$が与えられる。
$2$行目に各カードに書かれている整数が空白区切りで与えられる。

$2 \le N \le 16$
$-9 \le a_i \le 9$

出力

最大値を出力せよ。

サンプル

サンプル1
入力
4
0 -9 1 5
出力
50

$0 \ - \ (-9) \ + \ 1 \ × \ 5 \ = \ 50$

サンプル2
入力
8
6 6 1 3 3 2 2 -1
出力
1333

サンプル3
入力
16
6 9 1 2 1 2 1 2 1 4 1 4 1 8 1 2
出力
114514

提出ページヘ