$O(N^2)$ DP

DP：

定义 f[i] 表示到达第 i 层时能获得的最大价值。

使用前缀和数组 sum 来记录到达每一层时的总金币数。

状态转移：

直接在第 $i$ 层购买珠宝：$f[i] = sum[i] / i * a[i]$

从第 $j$ 层（ $j < i$ ）跳到第 $i$ 层后购买珠宝：$f[i] = max(f[i], f[j] + (sum[i] - sum[j]) / i * a[i])$

初始化：

$sum[0] = y$（初始金币）。

$sum[i] = sum[i-1] + k[i]$（每层获得初始金币奖励）。

结果计算：

遍历所有层数，更新 $f[i]$ 并记录最大值 $ans$。

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef pair<LL, LL> PII;

#define x first
#define y second

const int N = 2e5 + 10, M = 30;

int a[N], k[N];
LL sum[N], f[N];

void solve() 
{
    int n, m;
    cin >> n >> m;
    sum[0] = m;
    for(int i = 1; i <= n; i ++)
    {
        cin >> k[i];
        sum[i] = sum[i - 1] + k[i];
    }
    
    for(int i = 1; i <= n; i ++)
        cin >> a[i];
    
    LL ans = 0;
    for(int i = 1; i <= n; i ++)
    {
        f[i] = sum[i] / i * a[i];
        ans = max(ans, f[i]);
    }
    
    for(int i = 1; i <= n; i ++)
    {
        for(int j = 1; j < i; j ++)
            f[i] = max(f[i], f[j] + (sum[i] - sum[j]) / i * a[i]);
        ans = max(ans, f[i]);
    }
    cout << ans << endl;
    
}            

int main()
{
    int t = 1;
    // cin >> t;
    while(t --)
        solve();
}