VM 14 Bài 05 - Quá béo

View as PDF

Submit solution

Points: 0.77 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
VNOI Marathon 2014
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Cân nặng đã ở mức đáng báo động, admin ~K~ quyết định tập chạy để giảm cân. Khu vực admin ~K~ sống có một con đường dài, điểm đầu của con đường là điểm ~0~, điểm cuối của con đường là điểm ~N-1~. Các điểm cách đều nhau một khoảng ~1~ đơn vị độ dài; điểm thứ ~i~ có độ cao ~H_i~. Admin ~K~ muốn chọn ra một đoạn đường để tập chạy sao cho:

  • Đoạn đường có chiều dài ít nhất là ~L~.
  • Chênh lệch độ cao giữa điểm cao nhất và điểm thấp nhất trên đoạn đường không vượt quá ~D~.

Bạn hãy giúp xác định xem có bao nhiêu đoạn đường thỏa mãn.

Input

  • Dòng đầu tiên ghi ba số ~N~ ~L~ ~D~.
  • Dòng thứ hai ghi ~N~ số ~H_i~ là độ cao của điểm thứ ~i~.

Output

In ra số đoạn đường thỏa mãn.

Giới hạn

  • ~1 \le L < N \le {10}^6~
  • ~0 \le D \le {10}^4~
  • ~1 \le H_i~ ~\le {10}^4~
  • Trong ~15~% số test, ~N \le 500~
  • Trong ~20~% số test tiếp theo, ~N \le {10}^4~
  • Trong ~25~% số test tiếp theo, ~N \le {10}^5~

Sample Input

10 3 4
5 6 9 7 4 3 5 6 8 8

Sample Output

5

Comments

Please read the guidelines before commenting.


There are no comments at the moment.