問題一覧 > 通常問題

No.3129 Multiple of Twin Subarray

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 91
作問者 : 👑 loop0919 / テスター : lif4635 Iroha_3856 ルク
2 ProblemId : 12002 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-04-24 23:22:57

問題文

茜ちゃんと葵ちゃんは誕生日プレゼントとして数列を貰いました。

$2$ 人はその中から連続部分列をそれぞれ入手しようとしています。

長さ $N$ の数列 $A = (A_1, A_2, \cdots, A_N)$ が与えられます。
$2$ つの空でない互素な $A$ の連続部分列 $B, C$ について、$(B$ の総和$) \times (C$ の総和$)$ としてあり得る最大値を求めてください。

ここで $A$ の $2$ つの連続部分列 $(A_l, A_{l + 1}, \cdots, A_r), ~(A_L, A_{L + 1}, \cdots, A_R)$ が互素であるとは、区間 $[l, r]$ と区間 $[L, R]$ に共通部分がないことを指します。

制約

  • $2 \leq N \leq 2 \times 10^5$
  • $-10^4 \leq A_i \leq 10^4$
  • 入力はすべて整数

    • 入力

    入力は以下の形式で標準入力から与えられます。

    $N$
$A_1$ $A_2$ $\ldots$ $A_N$

    出力

    $(B$ の総和$) \times (C$ の総和$)$ としてあり得る最大値を出力してください。

    サンプル

    サンプル1
    入力
    5
-20 10 30 20 -20
    出力
    800

    $B = (10, 30), C = (20)$ と選ぶと、$(10 + 30) \times 20 = 800$ となり、これが最大です。

    サンプル2
    入力
    2
-1234 5678
    出力
    -7006652

    サンプル3
    入力
    9
-9 9 -8 2 -4 4 -3 5 -3
    出力
    90

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