P5653 Basic Optimization Practice Problem.

YSGH is our red sun.

YSGH has a number $x$ with initial value $0$. For the next $n$ minutes, each minute YSGH can add an integer $y$ to $x$, where $y \in [-k, k]$. At the same time, YSGH must ensure that at the end of the $i$-th minute, $x \le a_i$. Let $b_i$ be the value of $x$ at the end of the $i$-th minute. Now YSGH gives you a sequence $w$ of $n$ numbers. You need to maximize $\displaystyle \sum_{i = 1}^{n} b_i w_i$. You only need to output the maximum value.

The first line contains two positive integers $n, k$, with the same meaning as in the statement. The second line contains $n$ integers, where the $i$-th integer is $a_i$, with the same meaning as in the statement. The third line contains $n$ integers, where the $i$-th integer is $w_i$, with the same meaning as in the statement. It is guaranteed that the input ensures there exists at least one sequence $b$ that satisfies the conditions.

The first line contains one integer, which is the answer.

For $10\%$ of the data, $n \le 10$, $k \le 1$. For $20\%$ of the data, $n \le 100$. For $30\%$ of the data, $n \le 10^3$. For $50\%$ of the data, $n \le 10^4$. There is another $10\%$ of the data where $w_i \ge 0$. For $100\%$ of the data, $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$. Translated by ChatGPT 5