| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 271 | 88 | 76 | 32.479% |
폭탄의 악마에게 x축 수직선 상에 있는 모든 폭탄을 터뜨리라 의뢰가 들어왔다. 현재 x축 수직선 상에는 총 $N$개의 폭탄이 있으며, 그중 $i$번째 폭탄의 폭발 비용은 $C_i$이다.
폭탄의 악마는 우선 원하는 만큼 폭탄을 선택할 수 있으며, 이때 총 폭발 비용은 선택한 폭탄의 폭발 비용의 합이다. 그 후, 힘을 $1$ 이상의 정수 $R$만큼 사용하여 선택한 모든 폭탄을 $R$만큼의 폭발 반경을 가지고 터뜨릴 수 있다. 이때, 폭탄이 터질 경우에 해당 폭탄의 반경 $R$ 내의 다른 모든 폭탄은 연쇄적으로 터지게 된다. 연쇄적으로 터진 폭탄도 마찬가지로 반경 $R$ 내의 다른 폭탄을 터뜨릴 수 있으며, 이는 반경 내에 더 이상 터질 폭탄이 없을 때까지 계속된다.
의뢰를 성공하려면 폭탄의 악마가 받은 의뢰 비용 $B$ 내에서 모든 폭탄이 터지도록 해야한다. 또한, 폭탄의 악마는 자신의 힘 $R$을 최소한으로 사용하고 싶어한다. 폭탄의 악마를 위해 의뢰 비용 $B$ 내에서 모든 폭탄이 터지도록 하는 폭탄의 악마의 힘 $R$의 최솟값을 구해주자.
첫째 줄에 폭탄의 수 $N$이 주어진다. ($ 2 \le N \le 200\,000 $)
둘째 줄에 폭탄의 위치를 의미하는 정수 $X_1, X_2, \cdots , X_N$이 공백으로 구분되어 주어진다. $X_i$는 중복되어 주어지지 않는다. ($ -10^8 \le X_i \le 10^8 $)
셋째 줄에 비용을 의미하는 정수 $C_1, C_2, \cdots , C_N$이 공백으로 구분되어 주어진다. ($ 1 \le C_i \le 10\,000$)
넷째 줄에 폭탄의 악마가 받은 의뢰 비용을 의미하는 정수 $B$가 주어진다. ($ \min(C_i) \le B \le 10\,000\,000 $)
의뢰 비용 $B$ 내에서 모든 폭탄이 터지도록 하는 폭탄의 악마의 힘 $R$의 최솟값을 출력한다.
5 1 3 6 10 13 5 2 3 4 1 7
3
7 4 11 0 2 7 15 20 2 8 3 6 5 1 4 10
4
University > 서울시립대학교 > 2025 서울시립대학교 프로그래밍 경진대회 (UOSPC) F번