C - 総和
Editorial
/


Time Limit: 2 sec / Memory Limit: 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
オーバーフローに注意してください。