問題一覧 > 通常問題

No.1977 Extracting at Constant Intervals

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 25
作問者 : magstamagsta / テスター : tassei903tassei903
2 ProblemId : 8121 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-06-10 12:46:49

問題文

$N$ 個の要素でできた整数列 $A_1,A_2,\dots,A_N$ と整数 $M,L$ が与えられます。

整数列 $A$ を $M$ 個連続に繋げて作られる長さ $NM$ の数列を $B$ とします。


$1 \leq i \leq L$ を満たす $i$ を取ることを考えます。このとき、$C_i$ を以下のように定義します。

  • $j \equiv i \pmod L, 1 \leq j \leq NM$ を満たす全ての $j$ に対する $B_j$ の総和

    • $C_i$ の最大値を求めてください。

    制約

    • $\displaystyle 1 \leq N \leq 10^5$
    • $\displaystyle 1 \leq M \leq 10^9$
    • $\displaystyle 1 \leq L \leq NM$
    • $\displaystyle -10^4 \leq A_i \leq 10^4 \ (1 \leq i \leq N)$
    • 入力はすべて整数である

    入力

    $N\ \ M\ \ L$
$A_1\ \ A_2\ \ \dots\ \ A_N$

    出力

    求めた値を出力し、最後に改行せよ。

    サンプル

    サンプル1
    入力
    5 2 3
4 -6 3 5 -1
    出力
    12

    数列 $B$ は $B={4,-6,3,5,-1,4,-6,3,5,-1}$ となります。

    $C_1=2,C_2=-4,C_3=12$ となり、最大値は $12$ です。

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

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