29755번 - 블랙홀과 소행성 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 834 | 277 | 237 | 35.964% |
문제
현재 시뮬레이션 우주에는 수직선 위에 블랙홀 $N$개와 소행성 $M$개가 존재한다. 블랙홀 $N$개의 끌어당기는 힘은 $P$로 같다.
블랙홀 $i$의 위치가 $b_i$고, 소행성 $j$의 위치를 $a_j$, 질량을 $w_j$라고 했을 때, 이 시뮬레이션 우주에서는 $\vert b_i - a_j \vert \leq \frac{P}{w_j}$ 인 경우, 블랙홀 $i$가 소행성 $j$를 끌어와 빨아들인다. $(1 \le i \le N;$ $1 \le j \le M)$
하나의 블랙홀이 여러 소행성을 빨아들이는 것도 가능하며, 서로 다른 여러 블랙홀이 하나의 소행성을 끌어들일 수 있을 땐 위치가 가장 왼쪽에 있는 블랙홀이 소행성을 빨아들인다.
시뮬레이션 우주에 있는 모든 소행성을 블랙홀이 빨아들이기 위해 필요한 정수 $P$의 최솟값을 구하는 프로그램을 작성하시오.
입력
첫 번째 줄에 블랙홀의 수 $N$과 소행성의 수 $M$이 공백으로 구분되어 주어진다. $(1 \le N, M \le 200\,000)$
두 번째 줄에 $N$개의 정수 $b_1$, $b_2$, $\cdots$, $b_N$이 공백으로 구분되어 주어진다. $(-1\,000\,000 \le b_i \le 1\,000\,000)$
세 번째 줄부터 $M$개의 줄에 걸쳐 소행성의 정보가 주어진다. 그중 $j$번째 줄에는 정수 $a_j$, $w_j$가 공백으로 구분되어 주어진다. $(-1\,000\,000 \le a_j \le 1\,000\,000;$ $1 \le w_j \le 100)$
한 위치에는 블랙홀만 하나 존재하거나 소행성만 하나 존재할 수 있다.
출력
모든 소행성을 블랙홀이 빨아들이기 위해 필요한 정수 $P$의 최솟값을 출력한다.
예제 입력 1
2 3 1 5 2 3 7 1 4 2
예제 출력 1
3
노트
$|x|$는 $x$의 절댓값을 의미하며, $x \ge 0$이면 $\vert x \vert = x$이고, $x < 0$이면 $\vert x \vert = -x$다.
출처
University > 국민대학교 > 2023 국민대학교 알고리즘 콘테스트 > 2023 국민대학교 알고리즘 콘테스트 F번
University > 중앙대학교 > 중앙대학교 프로그래밍 경진대회 (CPC) > 2023 중앙대학교 프로그래밍 경진대회 (CPC) > Division 1 D번
University > 중앙대학교 > 중앙대학교 프로그래밍 경진대회 (CPC) > 2023 중앙대학교 프로그래밍 경진대회 (CPC) > Division 2 E번
University > 중앙대학교 > 중앙대학교 프로그래밍 경진대회 (CPC) > 2023 중앙대학교 프로그래밍 경진대회 (CPC) > Open Contest E번
University > 국민대학교 > 2023 국민대학교 알고리즘 콘테스트 > Open Contest E번
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호