P7287 "EZEC-5" Magic

Xiao Ming is a magician. He has a sequence $A$ that can be enchanted. He has two kinds of magic: 1. Spend $a$ mana, choose an interval $[l,r]$ in $A$, and add $1$ to all of $A_{l},A_{l+1}...A_{r}$. 2. Spend $b$ mana, choose an interval $[l,r]$ in $A$, and multiply all of $A_{l},A_{l+1}...A_{r}$ by $2$. Now Xiao Ming wants to cast magic on the sequence $A$ several times so that there exists a sub-interval whose element sum is at least $s$. Please output the minimum mana cost that Xiao Ming needs to spend.

The first line contains four integers $n,a,b,s$, representing the sequence length, the costs of the two kinds of magic, and the required sum. The next line contains $n$ integers, representing the initial sequence.

One integer, representing the minimum cost.

[This problem uses bundled testdata.] For $10\%$ of the testdata, $n \leq 5$, $|A_i|,s \le 100$. For another $20\%$ of the testdata, $n = 10^3$. For another $5\%$ of the testdata, $A_i \ge 0$. For another $25\%$ of the testdata, $a,b \le 3$. For $100\%$ of the testdata, $1 \leq n \leq 10^{5}$, $1 \leq a,b \leq 10^9$, $-10^{9} \leq A_{i} \leq 10^{9}$, $1 \leq s \leq 10^{9}$. [Sample Explanation]: For the sample, one of the best methods is to use Magic 1 once to change (1,4), use Magic 1 three times to change (2,5), and use Magic 2 three times to change (2,5). ``` -3 -1 1 -2 0 -2 0 2 -1 0 -2 1 3 0 1 -2 2 4 1 2 -2 3 5 2 3 -2 6 10 4 6 -2 12 20 8 12 -2 24 40 16 24 -2+24+40+16+24 >= 102 ``` Translated by ChatGPT 5