문제
곧 졸업을 앞두고 있는 준혁이는 친구들과 기념사진을 찍어 추억을 남기려고 한다. 그러나 준혁이와 친구들이 방문한 사진관은 다음과 같은 특별한 조건들을 요구했다.
N명의 친구들이 일렬로 줄을 서서 사진을 여러 장 찍으며, 모든 친구들이 적어도 한 장의 사진에 최소 한번씩 등장하게 사진을 촬영하고자 한다. 사진을 촬영하는 방법은 다음과 같다.
1. 한 사람의 독사진을 촬영한다. 이 때 드는 비용은 그 사람의 고유한 비용 A_i원이다.
2. 원하는 위치의 인접한 두 사람의 위치를 바꾼다. 이 때 드는 비용은 C원이다.
3. 연속한 구간에 놓여 있는 친구들의 단체 사진을 촬영한다. 이 때 드는 비용은 사진에 찍히는 한 사람당 B원으로, 전체 비용은 B * (구간 길이) 이다. 단, 기술적인 문제로 단체 사진에는 K명 이상의 친구들이 나와야만 촬영할 수 있다.
현재 친구들은 이미 일렬로 서서 사진 촬영만을 기다리고 있다. 준혁이를 도와 모든 친구들이 적어도 한 장의 사진에 최소 한번씩 등장하도록 사진을 찍을 때의 최소 비용을 구하도록 하자.
입력
첫 번째 줄에 N, K, B, C가 공백으로 구분되어 주어진다. (1 <= N <= 5,000, 1 <= K <= N, 1 <= B <= 10^9, 1 <= C <= 10^9)
다음 줄에 N개의 정수 A_i이 주어진다. (1 <= A_i <= 10^9)
출력
첫 번째 줄에 모든 친구들이 적어도 한 장의 사진에 최소 한번씩 등장하도록 사진을 찍을 때의 최소 비용을 출력한다.
예제
6 3 25 3
33 9 31 35 8 35
123
출처
나는코더다 2021 송년대회, arnold518
로그인해야 코드를 작성할 수 있어요.