6132번 - 전화선 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 146 | 68 | 51 | 45.536% |
문제
재현이는 BOJ의 전화선을 공사하려고 한다.
BOJ에는 N개의 전신주가 있으며, 각 전신주는 Hi 의 높이를 가진다. 전화선은 1,2...N 번 전신주에 순서대로 설치되어야 하며, 이때 C * |두 전신주의 높이 차| 만큼의 비용이 든다.
재현이는 또한 전신주의 높이를 높일 수 있다. 만약 전신주의 높이를 X만큼 높였다면, X^2 만큼의 비용이 든다.
재현이는 적절히 전신주의 높이를 높이고 전화선을 설치해서 최소 비용으로 전화선을 공사하려고 한다. 재현이를 도와 전화선을 설치하는 최소 비용을 출력하라.
입력
첫째 줄에 N과 C가 주어진다. (1 <= N <= 100,000, 1 <= C <= 100)
이후 N개의 줄에 Hi가 주어진다. (1 <= Hi <= 100)
출력
재현이가 전화선을 설치하는 데 드는 최소 비용을 출력하라.
예제 입력 1
5 2 2 3 5 1 4
예제 출력 1
15
힌트
[3, 3, 5, 3, 4] 로 전신주의 높이를 바꾸면 15에 문제를 해결할 수 있으며 이것이 최소다.
출처
Olympiad > USA Computing Olympiad > 2007-2008 Season > USACO November 2007 Contest > Gold 1번
- 문제를 번역한 사람: koosaga
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호