27897번 - 특별한 화재 경보 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 512 MB | 98 | 48 | 45 | 72.581% |
문제
NLCS Jeju는 화재 경보가 자주 울리는 것으로 악명이 높다. 화재 경보가 울리는 이유는 여러 가지가 있는데, 그중 하나는 학생이 장난으로 경보를 울리는 경우이다. 오늘은 NLCS Jeju의 학생인 동호가 작정하고 화재 경보를 울렸다.
화재 경보가 울리면 교실에 있는 $N$명의 학생들은 모두 운동장으로 나가 한 줄로 서야 한다. 모든 학생은 키가 서로 다르고, 학생들에게는 키순으로 $1$번에서 $N$번까지의 번호가 붙어 있다. 학생들이 운동장으로 이동할 때 항상 질서를 잘 지키는 것은 아니기 때문에, 학생들은 초기에 키순으로 서 있지 않을 수도 있다.
학생들이 운동장에 모이면, 선생님은 $1$번부터 $N$번까지 학생들이 모두 모였는지 확인한다. 어떤 학생 $i$보다 키가 큰 학생이 $i$ 앞에 없다면, $i$번 학생을 확인하는 데는 시간이 걸리지 않는다. 그러나, $i$보다 키가 큰 학생이 $i$ 앞에 $k$명 있다면, 학생 $i$가 있다는 사실을 순서대로 앞으로 전달해 주어야 하기 때문에 시간이 $k$초 더 걸린다. 이렇게 모든 학생을 확인하는 데 걸린 시간의 합이 확인 절차에 걸리는 전체 시간이다.
그런데 동호는 화재 경보를 울릴 때부터 수업을 하는 시간을 최대한 줄이고 싶었기 때문에, 확인 절차에 걸리는 전체 시간을 최대한 늘리려고 한다. 이를 위해 동호는 최대 $L$번, 인접한 두 학생의 위치를 교환하려고 한다.
현재 $N$명의 학생들이 서 있는 순서와 정수 $L$이 주어질 때, 최대 $L$번의 행동을 수행한 후, 확인 절차에 걸리는 전체 시간의 최댓값을 구하는 프로그램을 작성하시오.
입력
첫 번째 줄에 두 개의 양의 정수 $N$과 $L$이 공백으로 구분되어 주어진다.
두 번째 줄에 $N$개의 양의 정수가 공백으로 구분되어 주어진다. $i$번째 정수는 줄의 $i$번째에 서 있는 학생의 번호를 의미한다. 모든 학생의 번호는 $1$ 이상 $N$ 이하이며, 모든 학생들은 번호가 서로 다르다.
출력
확인 절차에 걸리는 전체 시간의 최댓값을 나타내는 정수를 출력한다.
제한
- $1\leq N \leq 500\,000$
- $1\leq L \leq 10^{18}$
예제 입력 1
5 3 1 3 5 2 4
예제 출력 1
6
학생들의 순서를 세 번 바꿀 수 있기 때문에 다음과 같이 바꿔준다.
$(1\ 3\ 5\ 2\ 4)$ $\rightarrow$ $(3\ 1\ 5\ 2\ 4)$ $\rightarrow$ $(3\ 5\ 1\ 2\ 4)$ $\rightarrow$ $(3\ 5\ 2\ 1\ 4)$
첫 번째와 두 번째 학생을 확인하는 데는 시간이 걸리지 않는다. 세 번째 학생을 확인하는 데는 $2$초, 네 번째 학생을 부르는 데 $3$초, 다섯 번째 학생을 부르는 데 $1$초가 걸리기 때문에 답이 $6$초가 된다.
출처
High School > NLCS Jeju > GEC-Cup I번
- 문제를 만든 사람: dhyang24, joonseok_aaren_kang
- 문제를 검수한 사람: dohoon, eaststar, hjroh0315, jk410, kiwiyou, mjhmjh1104, parkky, sait2000
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호