問題一覧 > 通常問題

No.1334 Multiply or Add

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 30
作問者 : penguinmanpenguinman / テスター : 夕叢霧香(ゆうむらきりか)夕叢霧香(ゆうむらきりか)
2 ProblemId : 5459 / 出題時の順位表
問題文最終更新日: 2021-01-17 04:29:50

問題文

$N$ 項の式 $A_1\ op_1\ A_2,\ldots,op_{N-1}\ A_N$ を考えます。$A_i$ は正整数、$op_i$ は '+' または '×' の記号です。

$N$ と $A_1,\ A_2,\ldots,A_N$ が与えられるので、適切に $op_i$ に記号を代入することで式の結果を最大化し、最大値を出力してください。

これは非常に大きくなることがあるので、$10^9+7$ で割った余りを出力してください。

演算の優先順位は通常の式同様、掛け算 → 足し算の順に高いです。

入力

$N$
$A_1\ A_2\ldots A_N$
  • $2≤N≤2×10^5$
  • $1≤A_i≤10^9$
  • 入力は全て整数

出力

演算結果の最大値を $10^9+7$ で割った余りを出力してください。

サンプル

サンプル1
入力
4
2 1 3 1
出力
7

$2×1×3+1$ と $2+1+3+1$ が最大値を取ります。

サンプル2
入力
5
5 1 4 2 3
出力
120

$5×1×4×2×3$ が最大値を取ります。

サンプル3
入力
7
11032 193029 8284 13828 73476 1391 10
出力
518962052

$10^9+7$ で割った余りを求めてください。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。