시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 1024 MB | 108 | 44 | 37 | 43.529% |
날다람쥐 한 마리가 자유 낙하를 하려고 한다.
$N$개의 휴식점이 주어지고, 각각의 휴식점의 좌표 $X_i, Y_i$가 주어진다. 가장 많은 수의 휴식점을 지나가는 것이 날다람쥐의 목표이다.
안아줘요 날다람쥐는 언제나 안아줘요 포즈를 취하고 있기 때문에 공기 저항을 크게 받아 좌우 방향의 이동보다 빠르게 낙하할 수는 없다.
즉, $|Y_i - Y_j| ≤ |X_i - X_j|$이고 $Y_i > Y_j$인 경우에만 $i$번 휴식점에서 $j$번 휴식점으로 이동할 수 있다.
여러 낙하 경로 중에, 가장 많은 휴식점을 지날 수 있는 경로를 선택하여 낙하하려고 한다.
$Q$개의 출발 휴식점 번호가 주어질 때, 해당 휴식점에서 출발해서 지날 수 있는 휴식점의 수를 날다람쥐에게 알려주자.
입력은 아래와 같이 주어진다.
$N$ $Q$
$X_1$ $Y_1$
...
$X_N$ $Y_N$
$q_1$
...
$q_Q$
출발 휴식점에서 경유할 수 있는 최대 휴식점의 개수를 한 줄에 하나씩 출력한다. 출발 휴식점과 도착 휴식점도 출력하는 숫자에 포함한다.
5 3 8 8 6 7 7 6 5 5 4 4 1 2 3
5 4 3
University > 연세대학교 > 2022 연세대학교 프로그래밍 경진대회 L번