基础最优化练习题
题目背景
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$。
你只需要输出最大值即可。
输入输出格式
输入格式
第一行两个正整数 $n, k$,意义同题面描述。
第二行共 $n$ 个整数,第 $i$ 个表示 $a_i$,意义同题面描述。
第三行共 $n$ 个整数,第 $i$ 个表示 $w_i$,意义同题面描述。
保证输入数据使得至少存在一个序列 $b$ 满足条件。
输出格式
第一行一个整数,表示答案。
输入输出样例
输入样例 #1
5 1
4 3 2 3 2
5 7 -5 9 -10
输出样例 #1
24
说明
对于 $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$。