求序列（斜率优化DP）

题目描述:

我的O（n^2）标程是无法通过这道题目的------qq1010903229（出题人）

 

已知有一n项的单调递增序列a及b[1]，求序列b。

其中

b[i] = max( b[j]+a[i]+a[i]*a[j]-t*a[j])( 1<=j<i<=n )

输入格式:

第1行2个数n，t

第2行n个数a[1]-a[n]

第3行1个数b[1]

输出格式:

n个数b[1]-b[n]

样例输入:

5 4
1 2 3 4 5
3

样例输出:

3 3 5 9 18

提示:

数据由O（n^2）标程生成，最后一个点生成了20秒

直接将O（n^2）标程提交可得90分

3<=n<=100000

保证a[i]，b[i]，t在long long 范围之内

时间限制: 1000ms
空间限制: 256MB

---

来源: by qq1010903229