레이팅 미적용농부 존의 농장에는 N개의 언덕이 있으며 (1 <= N <= 1,000), 각 언덕의 고도는 0 .. 100 범위의 정수이다. 겨울에는 이 언덕들에 눈이 풍부하게 쌓이기 때문에, FJ는 정기적으로 스키 훈련 캠프를 운영한다.
안타깝게도 FJ는 스키 훈련 캠프로 사용되는 농장에 부과되는 새로운 세금에 대해 방금 알게 되었다. 하지만 법을 꼼꼼히 읽어 보니, 스키 캠프의 공식 정의는 소유지에서 가장 높은 언덕과 가장 낮은 언덕의 차이가 17보다 엄격히 커야 한다는 것을 발견했다. 따라서 가장 높은 언덕들을 깎고 낮은 언덕들에 흙을 더해 높이를 올리면, 가장 높은 언덕과 가장 낮은 언덕의 새로운 차이가 17 이하인 한 FJ는 세금을 내지 않을 수 있다.
언덕의 높이를 x 단위만큼 바꾸는 데 x^2 단위의 비용이 든다면, FJ가 지불해야 하는 최소 비용은 얼마인가? FJ는 각 언덕의 높이를 정수 단위로만 바꾸려고 한다.
첫째 줄에 정수 N이 주어진다.
둘째 줄부터 1+N번째 줄까지, 각 줄에 언덕 하나의 고도가 주어진다.
가장 높은 언덕과 가장 낮은 언덕의 차이가 17 단위 이하가 되도록 언덕들의 고도를 수정하는 데 FJ가 지불해야 하는 최소 비용을 출력한다.
skidesign.in · 출력을 쓸 파일 skidesign.out5
20
4
1
24
2118Output details: FJ keeps the hills of heights 4, 20, and 21. He raises the hill of height 1 to 4 (cost 9) and shortens the hill of height 24 to 21 (cost 9).
riseoj 작성
출처 올림피아드 > USACO > 2013-2014 > January > Bronze