시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 203 | 33 | 19 | 13.571% |
동현이는 바다 위에서 표류 중이다. 그에게 남은 것은 오직 작살 하나뿐. 배가 고파진 동현이는 작살로 물고기를 잡아보려고 한다. 동현이는 다음 그림과 같이 작살을 수직 아래 방향으로 던진다.
바닷속에는 $N$마리의 물고기가 살고 있는데, 편의상 $i$번째 물고기의 현재 위치를 구간 [$S_i$, $E_i$]로 나타내자.
그런데 물고기는 살아있기 때문에 계속 움직인다. $i$번째 물고기의 속도는 $V_i$인데, 항상 수평 방향으로만 일정한 속도로 움직인다. 따라서 $t$초 후 $i$번째 물고기의 위치는 구간 [$S_i + tV_i$, $E_i + tV_i$]로 나타낼 수 있다.
동현이는 $t \ge 0$인 시점에서 원하는 위치에 작살을 던질 수 있다.
만약 작살을 던진 위치가 물고기의 구간에 포함된다면 해당 물고기를 잡게 된다. 즉, $t$초 후에 작살을 위치 $x$에 던졌다고 하자. 만약 $S_i + tV_i \le x \le E_i + tV_i$이면 $i$번째 물고기를 잡은 것이다.
작살이 던져지는 속도는 매우 빠르기 때문에 무시할 수 있다. 오직 작살을 한 번만 던질 수 있을 때, 최대 몇 마리의 물고기를 잡을 수 있는지 구해보자.
첫째 줄에는 물고기의 마릿수 $N$이 주어진다. ($1 \le N \le 1,000$)
둘째 줄부터 $N$개의 줄에 걸쳐 3개의 정수 $S_i$, $E_i$, $V_i$가 주어진다. ($-1,000,000 \le S_i, E_i, V_i \le 1,000,000$, $S_i < E_i$)
잡을 수 있는 최대 물고기 마릿수를 출력한다.
3 2 3 1 0 1 2 -2 -1 3
3
3 0 1 0 1 2 0 2 3 1
2
University > 경인지역 6개대학 연합 > shake! 2021 F번