「HNOI2021 省集 Day 1」数列
题目描述
给定长度为 n 的数列 A 和常数 C。将 A 划分成 m 个非空连续段。设 0=p0<p1<⋯<pm=n,第 j 段是区间 [pj−1+1,pj],其最大值记为 Bj。
求以下式子的最大值。
j=2∑m((Bj−Bj−1)2+C).
如果只划分成一段,式子的值为 0。
输入格式
第一行两个整数 n,C。第二行 n 个正整数 A1,A2,…,An。
输出格式
输出一行一个非负整数,表示最大值。
样例 1
5 3
10 1 2 3 5
103
样例 2
7 1
86 23 66 59 74 66 63
6694
样例 3
输入 · 输出
样例 4
输入 · 输出
数据范围
全部数据满足 2≤n≤106,1≤Ai≤106,0≤C≤1010。
| 原题测试点编号 |
n |
特殊性质 |
| 1 |
≤100 |
保证 Ai≤103 |
| 2 |
| 3 |
≤500 |
无 |
| 4 |
| 5 |
≤2×103 |
| 6 |
≤5×103 |
| 7 |
≤2×105 |
| 8 |
| 9 |
≤106 |
保证 A 数列单调不降 |
| 10 |
无 |