No.1334 Multiply or Add
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 35
作問者 :
penguinman
/ テスター :
夕叢霧香(ゆうむらきりか)
タグ : / 解いたユーザー数 35
作問者 :
penguinman
/ テスター :
夕叢霧香(ゆうむらきりか)
問題文最終更新日: 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もしくは右上の雲マークをクリックしてアカウントを作成してください。