题解 CF1703G Good Key, Bad Key

先放个代码。

int n, k;
cin >> n >> k;
vector<vector<int>> a(n + 5, vector<int>(35));
for (int i = 1; i <= n; i ++ )
{
    cin >> a[i][0];
    for (int j = 1; j <= 30; j ++ ) a[i][j] = a[i][j - 1] / 2;
}
vector<vector<LL>> f(n + 5, vector<LL>(35));
for (int i = 1; i <= n; i ++ )
{
    for (int j = 0; j <= min(i, 30); j ++ )
    {
        f[i][j] = -infLL;
        if (!j) f[i][j] = max(f[i][j], f[i - 1][j] + a[i][j] - k);
        else f[i][j] = max(f[i - 1][j] + a[i][j] - k, f[i - 1][j - 1] + a[i][j]);
    }
    if (i > 30) f[i][30] = max(f[i][30], f[i - 1][30]);
}
cout << *max_element(all(f[n])) << "\n";