#P5621. 「HNOI2021 省集 Day1」数列

    ID: 4622 传统题 1500ms 1024MiB 尝试: 15 已通过: 1 难度: 8 上传者: 标签>难度分类提高+/省选-动态规划线性 DPLi Chao 树优化 DP数据结构Li Chao 线段树CF2400

「HNOI2021 省集 Day1」数列

「HNOI2021 省集 Day 1」数列

题目描述

给定长度为 nn 的数列 AA 和常数 CC。将 AA 划分成 mm 个非空连续段。设 0=p0<p1<⋯<pm=n0=p_0<p_1<\cdots<p_m=n,第 jj 段是区间 [pj−1+1,pj][p_{j-1}+1,p_j],其最大值记为 BjB_j。

求以下式子的最大值。

∑j=2m((Bj−Bj−1)2+C).\sum_{j=2}^{m}\left((B_j-B_{j-1})^2+C\right).

如果只划分成一段,式子的值为 00。

输入格式

第一行两个整数 n,Cn,C。第二行 nn 个正整数 A1,A2,…,AnA_1,A_2,\ldots,A_n。

输出格式

输出一行一个非负整数,表示最大值。

样例 1

5 3
10 1 2 3 5
103

样例 2

7 1
86 23 66 59 74 66 63
6694

样例 3

输入 · 输出

样例 4

输入 · 输出

数据范围

全部数据满足 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 无