题意
给定数列 $a_1, a_2, \cdots, a_n$，可以对其进行下列操作。
- 花费 $a$ 魔法值，选择 $A$ 中的一个区间 $[l,r]$，将 $a_l, a_{l+1},\cdots, a_r$ 全部 $+1$.
- 花费 $b$ 魔法值，选择 $A$ 中的一个区间 $[l,r]$，将 $a_l, a_{l+1},\cdots, a_r$ 全部 $\times 2$.
现在可以做若干次操作，使得序列 $a$ 存在一个子区间，其元素之和不小于 $s$.
求需要花费的最小魔法值。
$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$.
题解
对于 $+1$ 操作，对整个序列都使用，一定不劣于只对序列的一段区间使用。
对于正数，直接 $\times 2$ 一定优于 $+1$.
对于负数，需要先做若干次 $+1$ 到正数，之后再 $\times 2$，这样最优。
因此最终的操作序列一定先加后乘，形如：
$$
+++\cdots++\times \times \times \cdots \times \times \times
$$
+++\cdots++\times \times \times \cdots \times \times \times
$$
由于 $1\leq s\leq 10^9$，若通过乘法操作能使区间和变大，则最多进行 $\log_2s$ 次乘法操作。
$\log_2 s < 30$，所以可以枚举乘法操作的次数。
对于加法操作的次数，可以二分解决。
二分，每次 $\rm{check}$ 时，先线性求出执行完操作之后的新序列 $b$，之后递推地求出最大子段和。
求最大子段和，只需设 $f_i$ 表示以 $i$ 结尾的最大子段和，$f_i=\max\{f_{i-1}+b_i, b_i\}$，$f$ 的最大值即为序列的最大子段和。
代码
#include <bits/stdc++.h>
#define int __int128
using namespace std;
inline int read() {}
inline void out(int x) {}
const int MAXN = 1e5 + 10, inf = 0x3f3f3f3f3f3f3f3f;
int n, va, vb, s, a[MAXN], b[MAXN], ans = inf;
bool check(int add, int Pow) {
for(int i = 1; i <= n; i++) b[i] = (a[i] + add) * Pow;
int curf = 0, maxf = 0;
for(int i = 1; i <= n; i++) {
curf = max(curf + b[i], b[i]);
maxf = max(maxf, curf);
}
return maxf >= s;
}
signed main() {
n = read(), va = read(), vb = read(), s = read();
for(int i = 1; i <= n; i++) a[i] = read();
//外层枚举乘法次数
for(int x = 0, Pow = 1; x <= 50; x++, Pow <<= 1ll) {
int l = 0, r = 1e15, mid, mmin = inf;
//内层二分加法次数
while(l <= r) {
mid = (l + r) >> 1ll;
if(check(mid, Pow)) r = mid - 1, mmin = mid;
else l = mid + 1;
}
if(mmin != inf)
ans = min(ans, vb * x + va * mmin);
}
out(ans); putchar('\n');
return 0;
}