P5653 基础最优化练习题

YSGH is our red sun.

YSGH 有一个数 $x$，初值为 $0$。接下来 $n$ 分钟，每分钟 YSGH 可以给 $x$ 加上整数 $y$，其中 $y \in [-k, k]$，同时 YSGH 需要保证第 $i$ 分钟结束时 $x \le a_i$。 设 $b_i$ 为第 $i$ 分钟结束时 $x$ 的值，现在 YSGH 给你一个 $n$ 个数的序列 $w$，你需要最大化 $\displaystyle \sum_{i = 1}^{n} b_i w_i$。 你只需要输出最大值即可。

无

无

对于 $10\%$ 的数据，$n \le 10$，$k \le 1$。 对于 $20\%$ 的数据，$n \le 100$。 对于 $30\%$ 的数据，$n \le {10}^3$。 对于 $50\%$ 的数据，$n \le {10}^4$。 另有 $10\%$ 的数据，$w_i \ge 0$。 对于 $100\%$ 的数据，$1 \le n \le {10}^6$，$-{10}^6 \le w_i \le {10}^6$，$0 \le a_i \le {10}^8$，$1 \le k \le 100$。