C - Reading Challenge Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 366 点

問題文

高橋君は N 日間の読書チャレンジに参加しています。第 i 日（ 1 \leq i \leq N ）には A_i ページを読む予定です。高橋君の読書速度は一定で、 1 ページ読むのに C 分かかります。

このチャレンジでは、連続する K 日以上の期間を選んで「読書期間」として報告できます。具体的には、 1 \leq l \leq r \leq N かつ r - l + 1 \geq K を満たす整数の組 (l, r) を選び、第 l 日から第 r 日までを読書期間とします。ただし、読書期間として報告できるのは、その期間の合計読書時間が制限時間 T 分以下である場合に限ります。第 l 日から第 r 日までの合計読書時間は C \times (A_l + A_{l+1} + \cdots + A_r) 分です。

報告可能な読書期間の個数を求めてください。すなわち、次の条件をともに満たす整数の組 (l, r) の個数を求めてください。

  • 1 \leq l \leq r \leq N かつ r - l + 1 \geq K
  • C \times (A_l + A_{l+1} + \cdots + A_r) \leq T

制約

  • 1 \leq N \leq 2 \times 10^6
  • 1 \leq C \leq 10^9
  • 1 \leq T \leq 10^{18}
  • 1 \leq K \leq N
  • 1 \leq A_i \leq 10^9（ 1 \leq i \leq N ）
  • 入力はすべて整数である

入力

N C T K
A_1 A_2 \cdots A_N
  • 1 行目には、日数を表す整数 N 、 1 ページあたりの所要時間（分）を表す整数 C 、制限時間（分）を表す整数 T 、読書期間の最小日数を表す整数 K が、スペース区切りで与えられる。
  • 2 行目には、第 i 日に読む予定のページ数を表す整数 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。

出力

条件を満たす組 (l, r) の個数を 1 行で出力せよ。

入力例 1

5 2 20 2
3 4 5 2 1

出力例 1

5

入力例 2

4 10 50 2
3 4 2 5

出力例 2

0

入力例 3

12 3 60 3
4 8 6 10 3 7 5 12 2 9 4 6

出力例 3

7

入力例 4

50 7 1000 5
12 25 7 30 18 22 15 9 40 11 13 27 5 34 20 16 8 29 24 6 10 31 19 14 28 17 21 4 35 23 26 12 9 33 7 18 25 11 30 6 15 22 13 27 5 20 16 8 24 10

出力例 4

147

入力例 5

1 1000000000 1000000000000000000 1
1000000000

出力例 5

1

Score : 366 pts

Problem Statement

Takahashi is participating in an N-day reading challenge. On day i (1 \leq i \leq N), he plans to read A_i pages. Takahashi's reading speed is constant, taking C minutes to read one page.

In this challenge, he can select a period of K or more consecutive days and report it as a "reading period." Specifically, he chooses a pair of integers (l, r) satisfying 1 \leq l \leq r \leq N and r - l + 1 \geq K, and designates the days from day l to day r as the reading period. However, a reading period can only be reported if the total reading time during that period is at most the time limit of T minutes. The total reading time from day l to day r is C \times (A_l + A_{l+1} + \cdots + A_r) minutes.

Find the number of reading periods that can be reported. That is, find the number of pairs of integers (l, r) that satisfy both of the following conditions:

  • 1 \leq l \leq r \leq N and r - l + 1 \geq K
  • C \times (A_l + A_{l+1} + \cdots + A_r) \leq T

Constraints

  • 1 \leq N \leq 2 \times 10^6
  • 1 \leq C \leq 10^9
  • 1 \leq T \leq 10^{18}
  • 1 \leq K \leq N
  • 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
  • All inputs are integers

Input

N C T K
A_1 A_2 \cdots A_N
  • The first line contains the integer N representing the number of days, the integer C representing the time (in minutes) per page, the integer T representing the time limit (in minutes), and the integer K representing the minimum number of days for a reading period, separated by spaces.
  • The second line contains the integers A_1, A_2, \ldots, A_N representing the number of pages planned to be read on day i, separated by spaces.

Output

Output the number of pairs (l, r) that satisfy the conditions, on a single line.

Sample Input 1

5 2 20 2
3 4 5 2 1

Sample Output 1

5

Sample Input 2

4 10 50 2
3 4 2 5

Sample Output 2

0

Sample Input 3

12 3 60 3
4 8 6 10 3 7 5 12 2 9 4 6

Sample Output 3

7

Sample Input 4

50 7 1000 5
12 25 7 30 18 22 15 9 40 11 13 27 5 34 20 16 8 29 24 6 10 31 19 14 28 17 21 4 35 23 26 12 9 33 7 18 25 11 30 6 15 22 13 27 5 20 16 8 24 10

Sample Output 4

147

Sample Input 5

1 1000000000 1000000000000000000 1
1000000000

Sample Output 5

1