P6173 [USACO16FEB] Circular Barn P

As a fan of modern architecture, Farmer John built a new circular barn. Inside the barn, there are $n$ rooms arranged in a ring ($3 \leq n \leq 1000$), numbered $1 \ldots n$ in clockwise order. Each room has doors to its left and right neighboring rooms, and also a door leading outside. FJ wants room $i$ to contain exactly $r_i$ cows ($1 \le r_i \le {10}^6$). To let the cows enter the barn in an orderly way, he plans to unlock $k$ doors from the outside into the barn ($1 \le k \le 7$). Then, each cow walks **clockwise** until it reaches its destination. FJ's goal is to minimize the total distance walked by all cows (the entry door for each cow can be chosen freely; the distance only counts walking after entering the barn). Please find this minimum total distance.

The first line contains two integers $n, k$. The next $n$ lines each contain an integer $r_i$ on line $i$.

Output the minimum total distance walked by all cows.

FJ opens doors $2$ and $5$. $11$ cows enter through door $2$ and go to rooms $2, 3, 4$, with a total distance of $8$. $10$ cows enter through door $5$ and go to rooms $5, 6, 1$, with a total distance of $6$. Translated by ChatGPT 5