23024번 - 보트 정박
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 (하단 참고) | 512 MB | 129 | 39 | 34 | 34.343% |
문제
Albert는 호숫가를 따라 보트 정박소를 운영하고 있다.
보트 정박소에는 총 n개의 작은 부두가 좌측에서 우측으로 1번부터 n번까지 번호가 붙어있다. i번째 부두는 길이가 P[i]이하인 보트를 정박할 때 이용할 수 있다. 각 부두에는 최대 한 대의 보트만 정박할 수 있다. 오늘 정박소에는 총 m대의 보트가 순서대로 진입할 예정이다 (진입하는 순서대로 1번부터 m번까지 번호가 붙어있다). j번째 보트의 길이는 B[j]라 하자.
각 보트는 아래 규칙에 따라 부두에 보트를 정박하거나 혹은 정박소를 통과한다.
- 각 보트는 좌측에서 진입하여 우측으로 진행하면서 해당 보트가 정박할 수 있는 비어있는 부두가 있다면 해당 부두에 정박한다. (가령 부두 i가 비어있고 P[i] ≥ B[j] 라면 j번째 보트는 부두 i에 정박할 수 있다.)
- 만약 정박할 수 있는 부두가 없다면 해당 보트는 정박하지 않고 빠져나간다.
예를 들어 n = 3, m = 5, P = [2, 2, 2], B = [1, 2, 3, 2, 1] 이라 하자 (아래 그림 참고).
이 때, 보트들이 순서대로 정박소를 통과하는 과정은 아래와 같다.
- 길이가 1인 1번 보트는 1번 부두에 정박한다. (좌측 그림 참고)
- 길이가 2인 2번 보트는 1번 부두가 비어있지 않으므로 2번 부두에 정박한다. (중간 그림 참고)
- 길이가 3인 3번 보트는 3번 부두가 비어있지만 보트의 길이가 너무 길어 정박할 수 없으므로 정박소를 통과한다.
- 길이가 2인 4번 보트는 3번 부두에 정박한다. (우측 그림 참고)
- 길이가 1인 5번 보트는 정박소를 통과한다.
모든 보트가 정박을 마치거나 정박소를 빠져나간 후, 각 부두 i에 정박한 보트의 번호를 A[i]라 하자. 만약 정박한 보트가 없다면 A[i] = 0으로 정의한다.
Albert는 A[1] × 1 + A[2] × 2 + ... + A[n] × n 값이 무엇인지 궁금하다 - Albert를 도와 이 값을 계산해주자. 위 예제의 경우, 마지막 보트가 정박소를 빠져나간 후 A = [1, 2, 4]가 되므로 정답은 17이다.
입력
첫 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스는 세 줄에 걸쳐 주어진다.
첫 줄에 n과 m이 공백으로 구분되어 주어진다.
둘째 줄에 n개의 정수가 (P[1], ..., P[n]) 공백으로 구분되어 주어진다.
셋째 줄에 m개의 정수가 (B[1], ..., B[m]) 공백으로 구분되어 주어진다.
출력
각 테스트 케이스의 답을 각 줄에 출력한다.
제한
- 1 ≤ T ≤ 3
- 1 ≤ n, m ≤ 200,000
- 1 ≤ P[i], B[j] ≤ 9 × 1018
예제 입력 1
2 3 5 2 2 2 1 2 3 2 1 5 5 1 2 1 2 1 2 1 2 1 2
예제 출력 1
17 28
예제 1: 본문에서 다루었다.
예제 2: A = [2, 1, 4, 3, 0]이 되어 정답은 28이다.
예제 입력 2
2 5 6 15 15 15 20 20 20 10 20 10 20 100 5 6 1 2 3 2 1 100 3 2 1 2 3
예제 출력 2
29 36
예제 1-2: 추가 설명 없음
시간 제한
- PyPy3: 20 초
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호