시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 | 1024 MB | 249 | 43 | 40 | 20.305% |
2차원 평면 위에 $N$개의 기둥이 일렬로 놓여 있다. 기둥들에는 왼쪽에서 오른쪽으로 $1$번부터 $N$번까지의 자연수 번호가 붙어 있다.
$i$ ($1 \le i \le N$)번째 기둥의 바닥은 점 $(D_i, 0)$에 위치하고, 높이는 $H_i$이다. 따라서 이 기둥은 점 $(D_i, 0)$와 $(D_i, H_i)$를 잇는 선분이다. 또한, $D_1 = 0$이다.
처음에 날다람쥐는 제일 왼쪽 기둥의 높이 $L$인 곳, 즉 점 $(0, L)$에 있다. 날다람쥐는 모든 기둥을 왼쪽부터 순서대로 거쳐서 제일 오른쪽 기둥의 높이 $R$인 곳, 즉 점 $(D_N, R)$에 가려고 한다.
날다람쥐가 한 기둥에서 다음 기둥으로 날아갈 때 오른쪽으로 $d$ ($d \ge 0$)만큼 움직이면 높이가 $d$만큼 감소한다. 다음 기둥에 도착하기 전에 땅에 닿으면 안 된다. 다음 기둥의 높이 $0$인 곳에 도착하는 것은 허용된다.
날다람쥐는 한 기둥에서 위로 기어오르거나 아래로 내려갈 수 있다. 기둥의 높이보다 더 높은 곳으로 오를 수는 없다. $i$번째 기둥에서 위로 $h$ ($h \ge 0$)만큼 오르면 $W_i \times h$의 비용이 든다. 기둥에서 아래로 내려갈 때는 비용이 들지 않는다.
아래 그림 1은 날다람쥐가 이동하는 한 가지 예이다.
그림 1
그림 2의 왼쪽처럼 이동하는 것은 중간에 땅에 닿은 경우가 있어 허용되지 않는다. 그림 2의 오른쪽처럼 이동하는 것은 기둥을 거치지 않은 경우가 있어 역시 허용되지 않는다.
그림 2
가장 작은 총 비용으로 날다람쥐가 목표 위치에 도착할 수 있는 방법을 계산하라.
여러분은 아래 함수를 구현해야 한다.
long long fly(vector<int> D, vector<int> H, vector<int> W, int L, int R)
D
의 D[
$i$]
는 $1$번째 기둥에서 $i+1$번째 기둥까지의 거리 $D_{i+1}$이다.H
의 H[
$i$]
는 $i+1$번째 기둥의 높이 $H_{i+1}$이다.W
의 W[
$i$]
는 $i+1$번째 기둥에서 거리 1을 올라갈 때의 비용 $W_{i+1}$이다.L
은 $1$번째 기둥에서 날다람쥐가 최초에 위치한 높이이다.R
은 $N$번째 기둥에서 날다람쥐가 도착해야 하는 높이이다.-1
이어야 한다.제출하는 소스 코드의 어느 부분에서도 입출력 함수를 실행해서는 안 된다.
$N = 3$이고 $1$번 기둥에서 $2$번 기둥까지의 거리는 $2$, $1$번 기둥에서 $3$번 기둥까지의 거리는 $5$, 기둥들의 높이는 왼쪽부터 각각 $8$, $5$, $5$, 기둥들의 가중치는 왼쪽부터 각각 $3$, $4$, $6$, $L=5$, $R=4$인 경우를 생각해 보자.
그레이더는 다음 함수를 호출한다.
fly([0, 2, 5], [8, 5, 5], [3, 4, 6], 5, 4) = 18
이 경우 $1$번 기둥에서 거리 $2$만큼을 올라가고, $3$번 기둥에서 거리 $2$만큼을 올라가는 것이 최적이므로 함수는 $18$을 반환해야 한다.
이 예제는 부분문제 3, 4, 5, 6의 조건을 만족한다.
Sample grader는 아래와 같은 형식으로 입력을 받는다.
Sample grader는 다음을 출력한다.
fly
가 반환한 값Sample grader는 실제 채점에서 사용하는 그레이더와 다를 수 있음에 유의하라.
Olympiad > 국제정보올림피아드 대표학생 선발고사 > 2022 > 1차 선발고사 4번
C++17, C++14, C++20, C++14 (Clang), C++17 (Clang), C++20 (Clang)