코스튬 파티

시간 제한1초메모리 제한128 MB

요약
두 소의 길이 합이 S 이하인 쌍의 개수를 구한다.
난이도

쉬움10점 중 3점

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

문제

핼러윈입니다! 농부 존은 소들을 코스튬 파티에 데려가려 하지만, 코스튬은 단 하나뿐입니다. 이 코스튬에는 정확히 소 두 마리가 들어가며 길이는 SS (1≤S≤1,000,0001 \le S \le 1{,}000{,}000)입니다. 존에게는 11번부터 NN번까지 번호가 매겨진 소 NN마리 (2≤N≤20,0002 \le N \le 20{,}000)가 있고, ii번 소의 길이는 LiL_i (1≤Li≤1,000,0001 \le L_i \le 1{,}000{,}000)입니다. 두 소는 길이의 합이 SS 이하일 때 함께 코스튬에 들어갈 수 있습니다. 서로 다른 두 소로 이루어진 쌍 중 코스튬에 들어갈 수 있는 쌍이 몇 개인지 구하세요.

입력

  • 첫째 줄: 공백으로 구분된 두 정수 NN과 SS
  • 둘째 줄부터 N+1N+1번째 줄까지: i+1i+1번째 줄에는 정수 LiL_i가 하나씩 주어집니다

출력

  • 길이의 합이 SS 이하인 서로 다른 두 소의 쌍의 개수를 나타내는 정수 하나를 출력합니다. 두 소의 순서는 구분하지 않습니다.

힌트

예제에서 코스튬 길이는 66이고 소들의 길이는 3,5,2,13, 5, 2, 1입니다. 조건을 만족하는 네 쌍은 길이 33과 22인 소, 길이 33과 11인 소, 길이 55와 11인 소, 길이 22와 11인 소입니다.

예제1

  1. 예제 1

    입력
    4 6
    3
    5
    2
    1
    
    예상 출력
    4