Trồng hoa

View as PDF

Submit solution


Points: 0.48 (partial)
Time limit: 0.6s
Memory limit: 512M
Input: stdin
Output: stdout

Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Pirate là một người rất yêu hoa. Anh ấy trồng một luống hoa trước cửa nhà mình. Luống hoa được chia thành các ô đất, mỗi ô đất trồng một bông hoa. Tuy nhiên, vì đang bị đau chân nên Pirate ấy không thể chăm sóc luống hoa một cách hoàn hảo nhất. Kết quả là các bông hoa của anh có xấu đẹp không đều nhau.

Để cải thiện tình hình, Pirate quyết định chỉ để lại hai khóm hoa rời nhau, mỗi khóm gồm một số các bông hoa đứng liên tiếp nhau. Để ngôi nhà của mình trông thật xinh đẹp, hai khóm hoa kia phải được chọn lựa kỹ càng. Anh dùng đôi mắt thẩm mỹ tinh tường của mình (gọi là "sắc kế") để đánh giá độ xinh đẹp của các bông hoa, được thể hiện bằng các số nguyên không âm. Căn cứ vào đó, một khóm hoa đạt tiêu chuẩn khi và chỉ khi chệnh lệch độ xinh đẹp giữa hai bông hoa bất kì trong khóm không quá một giá trị cho trước. Pirate muốn hai khóm hoa có càng nhiều bông hoa càng tốt. Bạn hãy giúp anh ấy xác định xem có thể chọn được nhiều nhất bao nhiêu bông nhé.

Input

  • Dòng ~1~: Hai số nguyên ~N~ - số bông hoa trên luống hoa, ~K~ - chênh lệch độ xinh đẹp tối đa của hai bông hoa bất kì trong một khóm.
  • ~N~ dòng tiếp theo: Mỗi dòng là một số nguyên thể hiện độ xinh đẹp của một bông hoa.

Output

  • Một số nguyên duy nhất là số bông hoa được chọn của hai khóm hoa.

Giới hạn

  • ~1 \leq N \leq 3 \times 10^{5}~.
  • ~30\%~ số test có ~1 \leq N \leq 30~.
  • ~50\%~ số test có ~1 \leq N \leq 10^{3}~.
  • Các số trong dữ liệu vào đều là số nguyên không âm không quá ~10^{9}~.

Sample Input 1

5 2
1 
3 
2 
5 
4

Sample Output 1

5

Sample Input 2

5 2
1 
3 
5 
2 
4

Sample Output 2

4

Note

  • Giải thích test ~1~: hai khóm hoa được chọn là ~(1~, ~2~, ~3)~ và ~(4~, ~5)~.
  • Giải thích test ~2~: hai khóm hoa được chọn là ~(1~, ~2)~ và ~(4~, ~5)~.

Comments

Please read the guidelines before commenting.


There are no comments at the moment.