26123번 - 외계 침략자 윤이 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 500 | 248 | 180 | 49.451% |
문제
외계인 윤이는 지구를 정복하고자 세계의 중심 도시인 울산을 침략했다. 울산에는 $N$개의 빌딩이 일렬로 늘어서 있고, 왼쪽에서 $i$번째 건물의 높이는 $h_i$이다.
윤이는 울산을 파괴하기 위해 다음과 같은 계획을 세웠다. 윤이는 매일 UFO를 타고 울산의 상공을 가르며 가장 높이가 높은 빌딩에 레이저를 발사할 것이다. 레이저에 맞은 빌딩은 높이가 $1$ 낮아진다. 만약 그 날에 가장 높이가 높은 빌딩이 여러 개라면, 해당하는 모든 빌딩에 레이저를 발사한다. 만약 이미 모든 빌딩의 높이가 $0$이 되었다면, 윤이는 더 이상 레이저를 발사하지 않는다.
윤이는 지금까지 $D$일 동안 계획을 착실하게 수행해 왔다. 윤이가 $D$일 동안 레이저를 발사한 총 횟수를 구하시오.
입력
첫 번째 줄에 건물의 개수 $N$과 윤이가 계획을 수행한 날의 수 $D$가 공백으로 구분되어 주어진다. ($1\le N\le 300\ 000$, $1\le D\le 300\ 000$)
두 번째 줄에 건물의 높이를 나타내는 $N$개의 정수 $h_i$가 공백으로 구분되어 주어진다. ($1\le h_i\le 300\ 000$)
출력
윤이가 $D$일 동안 레이저를 발사한 총 횟수를 출력한다. (32비트 정수 범위를 넘을 수 있음에 유의하라.)
예제 입력 1
5 3 1 3 2 5 4
예제 출력 1
6
- 처음 건물의 높이는 $[1,3,2,5,4]$이다.
- 첫 번째 날에 윤이는 레이저를 $1$회 발사하며, 건물의 높이는 $[1,3,2,4,4]$가 된다.
- 두 번째 날에 윤이는 레이저를 $2$회 발사하며, 건물의 높이는 $[1,3,2,3,3]$이 된다.
- 세 번째 날에 윤이는 레이저를 $3$회 발사하며, 건물의 높이는 $[1,2,2,2,2]$가 된다.
예제 입력 2
5 2 1 1 1 1 1
예제 출력 2
5
- 처음 건물의 높이는 $[1,1,1,1,1]$이다.
- 첫 번째 날에 윤이는 레이저를 $5$회 발사하며, 건물의 높이는 $[0,0,0,0,0]$이 된다.
- 두 번째 날에 이미 모든 건물의 높이가 $0$이므로 윤이는 레이저를 발사하지 않는다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호