問題一覧 > 通常問題

No.1977 Extracting at Constant Intervals

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

問題文

NN 個の要素でできた整数列 A1,A2,…,ANA_1,A_2,\dots,A_N と整数 M,LM,L が与えられます。

整数列 AA を MM 個連続に繋げて作られる長さ NMNM の数列を BB とします。


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

  • j≡i(modL),1≤j≤NMj \equiv i \pmod L, 1 \leq j \leq NM を満たす全ての jj に対する BjB_j の総和

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

    制約

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

    入力

    N  M  LN\ \ M\ \ L
A1  A2  …  ANA_1\ \ A_2\ \ \dots\ \ A_N

    出力

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

    サンプル

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

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

    C1=2,C2=−4,C3=12C_1=2,C_2=-4,C_3=12 となり、最大値は 1212 です。

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

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