Informatica Online Judge

  스키 코스 설계 [1160 / 0488]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 56   Total Tried : 64


The Champion of this Problem (C++) : gst19112 - ms / 359byte
My Best Submission (C++) : N/A

[USACO]

Background

농부 존의 농장에 올해 엄청나게 눈이 많이 왔다.

농부 존은 젖소들이 보다 즐겁게 놀기를 바라기 때문에 농장에 자신의 스키코스를 설계하고 있다.

스키장은 너무 위험하지 않도록 전체 영역에서 최고 높은 부분과 최고 낮은 부분의 크기 높이차가 17이하로 구성하고자 한다.

농부 존은 자신의 농장에 n개의 영역의 높이를 구하였다. 그리고 만약 최고 높은 부분과 낮은 부분의 높이차가 17을 초가하게 된다면, 낮은 부분을 좀 더 높여서 17이하로 만들거나, 높은 부분을 깎아서 17이하로 만들 수 있다.

한 영역에 대해서 x만큼을 깎거나 더 높이는데 x^2원의 비용이 든다고 한다.

현재 농장의 n개의 영역의 높이들이 주어질 때, 전체에서 가장 높은 곳과 낮은 곳의 높이차가 17이하가 되도록 하는데 드는 최소 비용을 구하시오.

Input

첫 번째 줄에 스키장 영역의 수 n이 입력된다.

다음 줄부터 n줄에 걸쳐서 각 영역의 높이가 입력된다.

[입력값의 정의역]
1 <= n <= 1,000
0 <= 각 영역의 높이 <= 100

Output

조건을 만족하는데 드는 최소비용을 출력한다.

IO Example

입력
5
20
4
1
24
21

출력
18

* 설명: 1을 4까지 3만큼 높이고, 24를 21까지 3만큼 내리면 모두 (3^2 + 3^2) = 18의 비용으로 높이차를 17이하로 만들 수 있다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]