VMQUABEO - Quá béo
Giới hạn- Thời gian: 1.0s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
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 <= L < N <= 10^6
- 0 <= D <= 10000
- 1 <= H[i] <= 10000
- Trong 15% số test, N <= 500
- Trong 20% số test tiếp theo, N <= 10^4
- Trong 25% số test tiếp theo, N <= 10^5
Example
Input: 10 3 4 5 6 9 7 4 3 5 6 8 8 Output: 5
- Người up: voj
- Nguồn bài: VNOI Marathon 2014