C. 圆形谷仓

    传统题 1000ms 256MiB

圆形谷仓

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

样例下载

题目描述

作为当代建筑的爱好者,Farmer John 建造了一个圆形新谷仓,谷仓内部 nn 个房间排成环形,按顺时针顺序编号为 1…n1\ldots n,每个房间都有通往与其相邻的左右房间的门。

现在 FJ 有 nn 头奶牛,他的目标是让每个房间恰好有一头奶牛。然而不幸的是,现在奶牛们随意呆在某个房间里,第 ii 个房间里有 cic_i 头奶牛。保证 ∑ci=n\sum c_i =n。

FJ 决定采用这样的方法来解决这个问题:让某些奶牛顺时针穿过某些房间到达指定的位置。如果一头奶牛穿过了 dd 扇门,他消耗的能量为 d2d^2。你需要帮 FJ 算出所有奶牛消耗的能量和最小值是多少。

输入格式

第一行一个整数 nn

接下来 nn 行,第 ii 行一个整数 cic_i。

输出格式

输出所有奶牛最小消耗能量和。

样例输入

6
1
0
0
2
0
3

样例输出

10

数据范围

20% 的数据:3≤n≤503 \leq n \leq 50

40% 的数据:3≤n≤1033 \leq n \leq 10^3

60% 的数据:3≤n≤5×1033 \leq n \leq 5×10^3

100% 的数据:3≤n≤1053 \leq n \leq 10^5

2026-11-14

未参加
状态
已结束
规则
OI
题目
4
开始于
2026-11-14 7:30
结束于
2026-11-14 12:00
持续时间
4.5 小时
主持人
参赛人数
14