Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

KDIFF - Trồng hoa

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/kdiff


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 ≤ N ≤ 3 * 105.
  • 30% số test có 1 ≤ N ≤ 30.
  • 50% số test có 1 ≤ N ≤ 103.
  • Các số trong dữ liệu vào đều là số nguyên không âm không quá 109.

Example

Input:
5 2
1
3
2
5
4

Output: 5

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

Output: 4

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

Được gửi lên bởi:khanhptnk
Ngày:2011-08-20
Thời gian chạy:0.400s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED

hide comments
2021-05-27 18:01:08
Tham khảo: https://vnspoj.github.io/problems/KDIFF
2020-06-27 13:43:58
Tham khảo:
Solution: http://megaurl.in/iGme3us
Code: http://megaurl.in/rq7Td8J
2020-04-01 23:38:45
dùng IT / RMQ 90 đ, deque 100 đ
2020-03-31 12:21:31
NlogN đ hiểu sao 33.33 đ ạ cay vcl
2020-03-14 15:53:56
1 đấm AC nlogn
2019-11-11 10:58:24
input 2 là sao vậy mọi người.
2019-09-24 17:04:39
1 đấm ko AC :)
duonght_pro_xinhgainhathemattroi_:)
2019-08-13 06:06:05
1 đấm AC :V :V
2019-06-19 14:27:23
86,67 mãi là sao :v test cục súc thế :v
2019-03-18 14:35:37
mình quá time sao vẫn 100 nhỉ :/
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.