#P2885. 数列

    ID: 1992 传统题 1000ms 512MiB 尝试: 26 已通过: 10 难度: 9 上传者: 标签>CF2600提高+/省选-线性 DPSlope Trick差分转化懒标记线段树线段树上二分标记复合

数列

题目描述

给定一个正整数序列 a1⋯na_{1\cdots n} 以及一个常数 cc。

现在你可以对于每一个 aia_i 分别加上一个数 xx,花费为 x2x^2,对于不同的 ii,xx 不需要相同。

完成所有操作之后,需要额外花费 c×∑i=2n∣ai−ai−1∣c\times \sum_{i=2}^n |a_i-a_{i-1}| 的代价。

最小化代价。

输入格式

第一行两个整数 n,cn,c。

第二行 nn 个整数表示 a1⋯na_{1\cdots n}。

输出格式

一行一个整数表示最小代价。

4 100
4
1
2
4
13

数据规模与约定

对于 50%50\% 的数据,1≤n≤1041\leq n\leq 10^4,1≤ai≤1001\leq a_i \leq 100。

对于 100%100\% 的数据,1≤n≤1051\leq n\leq 10^5,1≤ai≤1041\leq a_i\leq 10^4,1≤c≤1031\leq c\leq 10^3。