| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 0.5 초 | 512 MB | 278 | 101 | 73 | 36.683% |
Albert는 공작소를 운영한다. 오늘은 고객이 $N$개의 공작용 나무 막대를 가져왔는데 $i$번째 막대의 길이를 $S_i$라 하자. 고객은 길이가 1ドル$인 막대가 총 $K$개 필요한데, 자신이 가져온 막대를 필요한만큼 적절히 잘라주기 바란다. 이 공작용 막대는 특수 기계를 이용해서만 자를 수 있는데, 길이가 $L \ge 2$ 인 막대를 넣으면 아주 정밀하게 $L$개의 길이 1ドル$인 막대로 잘라주는 대신 길이에 비례하여 큰 비용이 발생한다. 구체적으로, 길이가 $L$인 막대를 넣으면 발생하는 비용은 $a \cdot (L - 1)^2 + b$ 이고 $a, b \ge 0$ 이다.
예를 들어 $N = 3,ドル $K = 8,ドル $S = [8, 4, 4],ドル $a = 1,ドル $b = 0$ 이라 하자.
다른 예로 $N = 4,ドル $K = 9,ドル $S = [3, 4, 5, 6],ドル $a = 1,ドル $b = 0$ 이라 하자.
입력으로 $N,ドル $K,ドル $a,ドル $b,ドル 그리고 $S$가 주어졌을 때, $K$개 이상의 길이 1인 막대기를 얻기 위해 최소로 필요한 비용을 계산해보자.
입력 첫 줄에 테스트 케이스의 수 $T$가 주어진다.
각 테스트 케이스의 첫 줄에는 $N,ドル $K,ドル $a,ドル $b$가 공백으로 구분되어 주어진다. 둘째 줄에는 막대기의 길이인 배열 $S$가 공백으로 구분되어 주어진다.
각 테스트 케이스의 정답을 각 줄에 출력한다.
6 3 8 1 0 8 4 4 4 9 1 0 3 4 5 6 6 2 2 5 1 2 3 1 2 3 6 8 2 5 1 2 3 1 2 3 6 10 2 5 1 2 3 1 2 3 6 4 0 1 3 3 3 3 3 3
18 25 0 26 33 2
예제 1-2: 본문에서 다루었다.
예제 3: 이미 길이 1인 막대가 2개 있으므로 추가 비용이 발생하지 않는다.
예제 4: 길이 3인 막대 두 개를 자르는 것이 최선이다.
예제 5: 추가 설명 없음.
예제 6: 길이 3인 막대 두 개를 자르면 된다. 길이 1인 막대가 6개 생기고, 이는 고객이 요구한 4개 이상을 만족시키므로 괜찮다.