시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 256 MB | 371 | 177 | 159 | 56.184% |
폴리매스 왕국의 중앙에 위치해 있는 빛의 돌은 사람들에게 빛을 공급합니다. 빛의 돌은 거리 $L$만큼 떨어진 곳까지 빛을 공급할 수 있습니다. 빛의 돌의 세기가 점점 약해지고 있기 때문에, 사람들은 빛의 돌의 위치를 옮겨서 모든 집에 빛의 돌이 공급될 수 있게 하려고 합니다.
빛의 돌을 옮길 위치는 이미 정해졌습니다. 문제는 빛의 돌을 옮기기 위해 큰 비용이 든다는 것입니다. 비용을 최소화하기 위해 빛의 돌을 끌고 가야 할지, 아니면 들고 가야 할지 정해야 합니다.
빛의 돌을 옮기게 될 길을 $N$개의 구간으로 나누면, $i$번 구간에서 빛의 돌을 끌고 가려면 $A_i$의 비용이 들고, 빛의 돌을 들고 가려면 $B_i$의 비용이 듭니다. 또한, 빛의 돌을 옮기는 방식을 바꿀 때마다 $K$의 추가 비용이 듭니다. (맨 처음과 맨 끝에는 추가 비용 $K$가 들지 않습니다.)
예를 들어, $N=3$, $K=2$, $A=[1, 7, 3]$, $B=[9, 3, 4]$라고 합시다. 돌을 옮기는 한 가지 방법은 전체 구간에서 끌고 가는 것으로, $1+7+3=11$의 비용이 필요합니다. 반면 첫 번째 구간에서는 빛의 돌을 끌어서 옮기고, 두세 번째 구간에서는 빛의 돌을 들어서 옮기면, $1+2+3+4=10$의 비용이 필요하므로 더 적은 비용으로 돌을 옮길 수 있습니다.
첫째 줄에는 구간의 개수 $N$과, 이동 방식을 바꿀 때 드는 비용 $K$가 주어집니다.
둘째 줄에는 빛의 돌을 끌고 갈 때 필요한 비용 $A_1, A_2, \cdots, A_N$이 주어집니다.
셋째 줄에는 빛의 돌을 들고 갈 때 필요한 비용 $B_1, B_2, \cdots, B_N$이 주어집니다.
빛의 돌을 옮기는 데 필요한 최소 비용을 출력합니다.
번호 | 배점 | 제한 |
---|---|---|
1 | 12 | $N \le 10$ |
2 | 5 | $K=0$ |
3 | 83 | 추가 제한 조건이 없습니다. |
3 2 1 7 3 9 3 4
10
Contest > 폴리매스 코드 챔피언십 > 폴리매스 제2회 코드 챔피언십 Division 2 C번