P3137 [USACO16FEB] Circular Barn S

*This problem has the same statement as the [problem with the same name in Gold](/problem/P6170); the only difference is the constraints.*

As an enthusiast of modern architecture, Farmer John built a new circular barn. Inside the barn, $n$ rooms are arranged in a ring ($3 \leq n \leq 1000$), numbered in clockwise order $1\ldots n$. Each room has doors to its two adjacent rooms, as well as a door to the outside. FJ has $n$ cows, and his goal is to have exactly one cow in each room. Unfortunately, the cows are currently scattered arbitrarily: room $i$ contains $c_i$ cows. It is guaranteed that $\sum c_i =n$. FJ decides to solve this by letting some cows move **clockwise** through rooms to their designated positions. If a cow passes through $d$ doors, it expends $d^2$ energy. You need to compute the minimal possible total energy expended by all cows.

The first line contains an integer $n$. The next $n$ lines each contain one integer $c_i$, where the $i$-th line contains $c_i$.

Output the minimal total energy expended by all cows.

Translated by ChatGPT 5