아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

조차장 <<Сортировочная>>

면접 대비

시간 제한2초메모리 제한512 MB

요약
서로 다른 질량을 가진 화차 n량이 일렬로 있을 때, 인접한 두 화차의 질량 합이 M 이하일 때만 맞바꿀 수 있다. 질량 오름차순으로 정렬할 수 있는지 판정한다.
난이도

보통10점 중 6점

유형
정렬, 그리디, 배열, 투 포인터
정답자
아직 제출이 없습니다

문제

철도 조차장 <<Сортировочная>>의 선로에는 nn량의 화물차가 있고, 이들로 열차를 편성해야 한다. 모든 화물차의 길이는 같지만 각 차에 서로 다른 화물이 실려 있어 질량은 다를 수 있다. <<Сортировочная>> 조차장의 작업자들은 화물차를 질량이 증가하는 순서로 늘어놓아야 하며, 그래야 열차가 출발할 수 있다.

보통 이런 작업에는 소위 입환용 디젤 기관차나 전기 기관차를 쓰지만, 이 조차장에서는 화차 정렬용 실험 장치를 시험하고 있다. 이 장치가 열차 편성에 드는 시간을 크게 줄여 줄 것으로 기대된다.

이 장치는 공기 부상 방식으로 화차 위를 이동하며, 길이는 화차 두 량의 길이보다 조금 길다. 장치는 인접한 두 화차 위에 떠서 둘 다 들어 올린 뒤 자리를 바꿀 수 있다. 다만 장치의 적재 능력이 제한되어 있어, 두 화차의 질량 합이 MM을 넘지 않을 때만 이 작업을 할 수 있다.

여러분이 할 일은 실험 장치를 써서 선로에 있는 화차를 필요한 순서로 늘어놓을 수 있는지 판별하는 프로그램을 작성하는 것이다.

입력

입력 파일의 첫째 줄에는 화차 수 nn (2≤n≤100 0002 \le n \le 100\,000)과 실험 장치의 적재 능력 MM (1≤M≤1091 \le M \le 10^9)이 주어진다. 둘째 줄에는 화차의 질량 m1m_1, \ldots, mnm_n이 주어진다. 이 질량은 1≤mi≤1091 \le m_i \le 10^9을 만족하며, 화차의 질량은 모두 서로 다르다. 화차의 질량은 입력 파일에 선로에 처음 놓여 있는 순서대로 나열된다.

출력

실험 장치를 써서 화차를 필요한 순서로 늘어놓을 수 있으면 <<Yes>>를, 아니면 <<No>>를 출력 파일에 출력한다.

예제2

  1. 예제 1

    입력
    4 10
    5 6 3 4
    
    예상 출력
    Yes
    
  2. 예제 2

    입력
    4 9
    5 6 3 4
    
    예상 출력
    No