레이팅 미적용현대 건축의 팬인 농부 존은 완벽한 원 모양의 새 헛간을 지었다. 헛간 내부는 둘레를 따라 시계 방향으로 \(1 \ldots n\) 번호가 붙은 \(n\)개의 방이 고리 모양으로 배치되어 있다 (\(3 \leq n \leq 100,000\)). 각 방에는 이웃한 두 방으로 통하는 문과, 헛간 바깥으로 통하는 문이 하나씩 있다.
농부 존은 소를 \(n\)마리 기르는데, 헛간의 각 방에 정확히 한 마리씩 들어가기를 원한다. 하지만 소들은 약간 혼란스러워하며 아무 문에나 줄을 서고, 여러 마리가 같은 문에 줄을 설 수도 있다. 정확히 \(c_i\)마리의 소가 방 \(i\)의 문 밖에 줄을 서므로 \(\sum c_i = n\)이다.
각 방에 소가 한 마리씩 들어가도록 소들을 모는 과정을 관리하기 위해, 농부 존은 다음 방식을 사용하려 한다. 각 소는 처음 줄을 선 문으로 들어간 뒤, 적절한 목적지에 도달할 때까지 방들을 시계 방향으로 걸어간다. 소가 문 \(d\)개를 통과하면 \(d^2\)의 에너지를 소모할 때, 각 방에 소가 한 마리씩 들어가도록 소들을 배치하는 데 필요한 최소 에너지를 구하여라.
출제자: Brian Dean
출제자: Brian Dean
입력의 첫째 줄에 \(n\)이 주어진다. 다음 \(n\)개의 줄에 \(c_1 \ldots c_n\)이 주어진다.
소들이 소모하는 최소 에너지를 출력한다.
cbarn.in · 출력을 쓸 파일 cbarn.out10
1
0
0
2
0
0
1
2
2
233riseoj 작성
출처 올림피아드 > USACO > 2015-2016 > February > Gold