#P6170. [USACO16FEB] Circular Barn G

[USACO16FEB] Circular Barn G

题目背景

本题与 银组同名题目 在题意上一致,唯一的差别是数据范围。

题目描述

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

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

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

输入格式

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

输出格式

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

10
1
0
0
2
0
0
1
2
2
2
33