#P17982. Potential Peak
Potential Peak
Potential Peak
题目描述
共有 天,第 天加入一名初始能力为 的成员,其编号为 。
在第 天结束时,对每名 的成员分别进行一次假想计算:他可以选择任意非负整数 ,花费 单位努力,把自己的能力临时提高到 。
对于每名满足 且 的成员 ,他得到 单位收益。其潜力值定义为“收益减去努力”所能达到的最大值,即
$$P_i(k)=\max_{e\in\mathbb Z_{\ge0}}\left(\#\{j:i<j\le k,\ a_i<a_j\le a_i+e\}-e\right).$$这些计算彼此独立,而且不会真正修改任何人的能力。求每一天结束时所有现有成员的潜力值之和。
输入格式
第一行一个整数 。第二行 个整数 。
输出格式
输出一行 个整数,第 个数为 。
数据范围
,。
样例 1
8
1 2 3 1 2 3 2 3
0 0 0 0 1 3 5 9
第 天,编号 的成员花费 ,可以得到编号 的两份收益,净收益为 ;其余成员潜力均为 。
样例 2
1
1
0