U220142 CF573E 加强版

听说这个题有 $O(n^2)$ 或 $O(n)$ 的做法。 听说原题真实难度为黄。

给定一个长度为 $n$ 的序列 $a_{1\dots n}$。你要求一个 $a$ 的子序列 $b_{1\dots m}$（可以为空），使得 $\sum_{i=1}^m ib_i$ 的值最大。

第一行为 $n$。 第二行为数列 $a_1\sim a_n$。

这个最大值。

$|a_i| \le 10^7$。std 能过且不用开 `__int128`。 $0\ pts:\color{white}\tiny\texttt{贪心。数据生成方式是正解和贪心对拍，卡掉一次贪心算一次数据。}$ $1\ pts:n=10010$。 $56\ pts:n=114514$。 $78\ pts:n=202205$。 $100\ pts: n=10^6$。 $\color{white}{听说正解+卡常可\ 100 pts（不是区间加等差数列）}$