#P9075. 「HNOI2021 省集 Day1」数列

    ID: 5160 传统题 1000ms 512MiB 尝试: 2 已通过: 1 难度: 8 上传者: 标签>CF2400提高+/省选-局部修复线性 DPLi Chao 树优化 DPLi Chao 线段树

「HNOI2021 省集 Day1」数列

题目描述

给定一个长度为 nn 的数列 AA 以及常数 CC,你需要将其划分成若干段,然后我们依次取出每一段的段内最大值,设这样得到的序列为 BB,你划分的段数为 mm。

你需要最大化:

∑i=2m((Bi−Bi−1)2+C)\sum^m_{i=2} ((B_i-B_{i-1})^2+C)

形式化的说:对于数列 AA,你需要选择若干个下标 1≤p1<p2<…<pm−1<n1 \le p_1 < p_2 < \ldots < p_{m−1} < n,

设 B1B_1 为数列 AA 中区间 [1,p1][1, p_1] 的最大值,对于 j∈[2,m−1]j \in [2, m − 1],BjB_j 为数列 AA 中区间 [pj−1+1,pj][p_{j−1} + 1, p_j ] 的最大值,BmB_m 为数列 AA 中区间 [pm−1+1,n][p_{m−1} + 1, n] 中的最大值。

你需要最大化:

∑i=2m((Bi−Bi−1)2+C)\sum^m_{i=2} ((B_i-B_{i-1})^2+C)

特别的,如果你划分出的段数仅有 11 段,则答案为 00。

输入格式

第一行两个整数分别表示 n,Cn,C。

接下来一行 nn 个正整数,第 ii 个正整数表示 AiA_i。

输出格式

一行一个非负整数,表示答案。

样例

样例 1

5 3
10 1 2 3 5
103

数据规模与约定

对于所有数据:2≤n≤1062\le n\le 10^6,1≤Ai≤1061\le A_i\le 10^6,0≤C≤10100\le C\le 10^{10}。

测试点编号 nn 特殊性质
11 ≤100\le 100 保证 Ai≤103A_i\le 10^3
22
33 ≤500\le 500 无
44
55 ≤2×103\le 2\times 10^3
66 ≤5×103\le 5\times 10^3
77 ≤2×105\le 2\times 10^5
88
99 ≤106\le 10^6 保证 AA 数列单调不降
1010 无