#PU621. USACO 2016 February Contest, Gold — Problem 1. Circular Barn

    ID: 1356 传统题 文件IO:cbarn 2000ms 256MiB 尝试: 0 已通过: 0 难度: 提高+/省选- 上传者: 标签>USACO赛事:feb16来源:usaco.orgscoring:equal_test_cases枚举二分答案

USACO 2016 February Contest, Gold — Problem 1. Circular Barn

USACO 2016 February Contest, Gold — Problem 1. Circular Barn

题目描述

Being a fan of contemporary architecture, Farmer John has built a new barn in the shape of a perfect circle. Inside, the barn consists of a ring of nn rooms, numbered clockwise from 1…n1 \ldots n around the perimeter of the barn (3≤n≤100,0003 \leq n \leq 100,000). Each room has doors to its two neighboring rooms, and also a door opening to the exterior of the barn. Farmer John owns nn cows, and he wants exactly one cow to end up in each room in the barn. However, the cows, being slightly confused, line up at haphazard doors, with possibly multiple cows lining up at the same door. Precisely cic_i cows line up outside the door to room ii, so ∑ci=n\sum c_i = n. To manage the process of herding the cows so that one cow ends up in each room, Farmer John wants to use the following approach: each cow enters at the door at which she initially lined up, then walks clockwise through the rooms until she reaches a suitable destination. Given that a cow walking through dd doors consumes d2d^2 energy, please determine the minimum amount of energy needed to distribute the cows so one ends up in each room.

输入格式

The first line of input contains nn. Each of the remaining nn lines contain c1…cnc_1 \ldots c_n.

输出格式

Please write out the minimum amount of energy consumed by the cows.

数据范围

(见题面原文)

样例

样例 1

10
1
0
0
2
0
0
1
2
2
2
33
Problem credits: Brian Dean