20314번 - 대홍수 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 226 | 89 | 71 | 47.020% |
문제
유니산맥에는 $N$개의 지역이 일렬로 늘어서 있고, 각 지역에는 주민이 살고 있다. 유니산맥의 길은 이웃한 지역 사이를 직선으로 잇는 길로만 구성되어 있다. 즉, 이웃하지 않은 지역을 이동하려면 사이에 있는 지역을 모두 거쳐야 한다. 유니산맥의 $i$번째 지역의 높이는 $h_i$미터이고, $i$번째 지역과 $i+1$번째 지역 사이를 이동하는 데 걸리는 시간은 $t_i$분이다. 모든 주민은 이웃한 두 지역 사이를 이동할 때 일정한 속도로 이동하며, 이동하는 데 동일한 시간이 걸린다.
어느 날 유니산맥에 큰 홍수가 나기 시작했다. 다행히도 이는 예언된 사실이었고, 유니산맥의 각 지역은 방주를 준비해 두어서 모든 주민들을 살릴 수 있다고 한다. 각 방주는 충분히 커서 탑승 인원에 제한이 없다. 유니산맥 주민들은 정든 유니산맥의 땅을 조금이라도 더 오래 밟고 싶었기 때문에, 이동 중에 물에 잠기지 않고 도달할 수 있는 가장 높은 지역에 있는 방주에 타려고 한다.
수면의 높이는 $0$미터에서 시작해서 $1$분에 $1$미터씩 일정한 속도로 차오른다. 주민이 이동하는 과정에서 수면의 높이보다 낮아지는 경우가 생기면 안 된다. 각 지역의 주민들이 도달할 수 있는 가장 높은 지역의 높이를 구하시오.
입력
첫 번째 줄에 지역의 수 $N$이 주어진다.
두 번째 줄에 각 지역의 높이를 나타내는 $N$개의 정수 $h_i$가 주어진다.
세 번째 줄에 이웃한 지역 사이를 이동하는 데 걸리는 시간을 나타내는 $N-1$개의 정수 $t_i$가 주어진다.
출력
한 줄에 $N$개의 정수 $m_i$를 공백으로 구분하여 출력한다.
$m_i$는 $i$번째 지역의 주민이 물에 잠기지 않고 도달할 수 있는 가장 높은 지역의 높이이다.
제한
- $2\le N\leq 200,000$
- $0\le h_i\le 10^9$
- $0< t_i \le 10^9$
서브태스크 1 (40점)
지역의 높이가 오름차순으로 정렬되어 있다. 즉, $h_i\le h_{i+1}$을 만족한다.
서브태스크 2 (120점)
추가적인 제약 조건이 없다.
예제 입력 1
10 3 5 2 8 4 7 6 2 4 4 4 1 2 2 3 2 2 2 1
예제 출력 1
5 8 8 8 8 8 7 7 7 4
$8$번째 지역에 사는 주민이 왼쪽으로 이동하면 다음과 같이 높이가 $7$인 $6$번 지역까지 이동할 수 있다.
- $2$분째에 $7$번째 지역에 도착하고, 그때의 높이는 $6$으로 수면의 높이인 $2$보다 높다.
- $4$분째에 $6$번째 지역에 도착하고, 그때의 높이는 $7$로 수면의 높이인 $4$보다 높다.
- 만약 $7$분째에 $5$번째 지역에 도착한다면 높이가 $4$가 되는데 수면의 높이인 $7$보다 낮으므로 조건을 만족하지 못한다. 따라서 $5$번째 지역이나 그 왼쪽으로 갈 수 없다.
출처
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호