페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#2616

[초등부] 2025 KOI 2차대회 대비 모의고사 (1회차)

명당
서브태스크
1초 1024MB

문제

도시는 일직선으로 늘어선 N개의 구역으로 구성되어 있다. 각 구역 i의 높이는 A_i이다.

정올이는 연속한 구역 중 최소 높이와 최대 높이의 차이가 K 이하인 곳을 명당이라고 생각한다.

그 중 가장 긴 명당의 길이를 구하는 프로그램을 작성하시오.


입력

첫 번째 줄에 정수 N, K가 주어진다. (1 ≤ N ≤ 200\ 000, 0 ≤ K ≤ 10^9)

두 번째 줄에 N개의 정수 A_1, A_2, \cdots, A_N이 주어진다. (0 \le A_i \le 10^9)


출력

첫 줄에 가장 긴 명당의 길이를 출력한다.


부분문제

번호 점수 조건
#110점

K=0

#220점

N \le 1\ 000

#330점

N \le 50\ 000

#420점

K=1

#520점

추가 제약 조건 없음


예제 

7 4
1 6 4 8 6 1 3
4

다음은 가능한 명당 자리들 중 일부이다.

  • 1 (최소 높이와 최대 높이 차이 0)

  • 6 4 8 6 (최소 높이와 최대 높이 차이 4)

  • 4 8 6 (최소 높이와 최대 높이 차이 4)

  • 8 6 (최소 높이와 최대 높이 차이 2)

  • 6 (최소 높이와 최대 높이 차이 0)

  • 1 3 (최소 높이와 최대 높이 차이 2)

가능한 모든 명당 자리들 중 가장 긴 명당 자리의 길이는 4다.

로그인해야 코드를 작성할 수 있어요.