C - 総和 解説 /

実行時間制限: 2 sec / メモリ制限: 256 MB

問題文

長さ N の数列 \{a_i\} と1 以上 N 以下の整数 K が与えられます。 この数列には長さ K の連続する部分列が N-K+1 個あります。これらのそれぞれ部分列に含まれる値の合計の総和を求めてください。

制約

  • 1 \leq K \leq N \leq 10^5
  • 0 \leq a_i \leq 10^8
  • a_i は整数である。

部分点

  • 50 点分のテストケースでは、 N \leq 10^3 である。

入力

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

N K
a_1 .. a_N

出力

部分列に含まれる値の合計 N-K+1 個の総和を出力せよ。

入力例 1

5 3
1 2 4 8 16

出力例 1

49

(1+2+4)+(2+4+8)+(4+8+16)=49 なので、答えは 49 です。

入力例 2

20 10
100000000 100000000 98667799 100000000 100000000 100000000 100000000 99986657 100000000 100000000 100000000 100000000 100000000 98995577 100000000 100000000 99999876 100000000 100000000 99999999

出力例 2

10988865195

オーバーフローに注意してください。