(Analysis by Danny Mittal)

Let $s$ be the given string, and $c$ be the given list of deletion costs.

Subtask $N \leq 2000$

We will use DP. Let $dp(k, x, j)$ be the minimum cost to delete characters in $s[1\dots k]$ so that we have $x$ occurrences of "bessie" as well as having the first $j$ characters of "bessie" at the very end (without any characters after). The answer will be $x$ and $dp(|s|, x, 0)$ for the largest $x$ such that the latter is finite.

There are two general transitions. The first is to transition from $dp(k - 1, x, j)$ to $dp(k, x, j)$ by deleting $s_k$, adding $c_k$ cost. The second occurs when $s_k$ is in a "bessie", in which case for all $j$ such that $s_k$ is the $j$th letter in "bessie" (with $j$ being $1$-indexed), we can go from $dp(k - 1, x, j - 1)$ to $dp(k, x, j)$ without adding any cost. Thus, we can compute the DP using the following equations. If $s_k$ is the $j$th character in "bessie",

$$dp(k, x, j) = \min(dp(k - 1, x, j) + c_k, dp(k - 1, x, j - 1)).$$
Otherwise,
$$dp(k, x, j) = dp(k - 1, x, j) + c_k.$$
Each of these transitions has a special case associated with $j = 0$. For the first one, because 'the first $0$ characters of "bessie" occurring at the end of the string' isn't actually a real constraint, we don't need to delete the added character to maintain it, so we can transition directly from $dp(k - 1, x, 0)$ to $dp(k, x, 0)$ without any added cost. For the second one we need to account for having a whole "bessie" at the end of the string that we would like to include in the count $x$. We can do this cleanly by transitioning from $dp(k, x - 1, 6)$ to $dp(k, x, 0)$. Thus, we can write
$$dp(k, x, 0) = \min(dp(k - 1, x, 0), dp(k, x - 1, 6)).$$
We therefore have a DP with $\mathcal O(|s|^2)$ states (because the amount of "bessie"s in $s$ is at most $\frac {|s|} 6$) with constant time transitions, giving an $\mathcal O(|s|^2)$ algorithm.

We can optimize the above DP by moving $x$ from the state to the value. The idea here is that because we want to maximize the number of "bessie"s first and minimize the cost second, a configuration that achieves $x$ "bessie"s with $y$ cost is always better than a configuration that achieves $x' < x$ "bessie"s and $y'$ cost regardless of if $y'$ is much smaller than $y$.

We can therefore define $dp(k, j)$ to be the optimal pair $(x, y)$ for deleting characters in $s[1\dots k]$ to end up with the first $j$ characters of "bessie" at the end, where $x$ is the number of additional "bessie"s in that string and $y$ is the cost. Optimality is then determined first by higher $x$ then by lower $y$.

The above transitions can be written as follows, with addition of pairs defined as $(a, b) + (c, d) = (a + c, b + d)$.

If $s_k$ is the $j$th character in "bessie",

$$dp(k, j) = \text{opt}(dp(k - 1, j) + (0, c_k), dp(k - 1, j - 1)).$$
Otherwise,
$$dp(k, j) = dp(k - 1, j) + (0, c_k).$$
And,
$$dp(k, 0) = \text{opt}(dp(k - 1, 0), dp(k, 6) + (1, 0)).$$
The number of states has been reduced to $\mathcal O(|s|)$ while the transitions are still constant time, giving a $\mathcal O(|s|)$ solution.

Python code that closely follows the analysis:

s = input()
c = list(map(int, input().split()))
BESSIE = "bessie"
INF = 300_000_000

def opt(a, b):
if a[0] > b[0]:
return a
if b[0] > a[0]:
return b
if a[1] < b[1]:
return a
return b

return (a[0] + b[0], a[1] + b[1])

dp = [[(-1, INF)] * 7 for _ in range(len(s) + 1)]
dp[0][0] = (0, 0)

for k in range(1, len(s) + 1):
for j in range(1, 7):
if s[k - 1] == BESSIE[j - 1]:
dp[k][j] = opt(add(dp[k - 1][j], (0, c[k - 1])), dp[k - 1][j - 1])
else:
dp[k][j] = add(dp[k - 1][j], (0, c[k - 1]))
dp[k][0] = opt(dp[k - 1][0], add(dp[k][6], (1, 0)))

bessies, cost = dp[len(s)][0]
print(bessies)
print(cost)


Ben's code:

s = input()
costs = map(int, input().split())

target = "bessie"
dp = [(float("-inf"), 0) for _ in target]
dp[0] = (0, 0)

for c, cost in zip(s, costs):
ndp = [(float("-inf"), 0) for _ in target]
for i in range(len(target)):
ndp[i] = max(ndp[i], (dp[i][0], dp[i][1] - (i > 0) * cost))
if target[i] == c:
j = (i + 1) % len(target)
ndp[j] = max(ndp[j], (dp[i][0] + 1, dp[i][1]))
dp = ndp

oc, minus_cost = max([(progress // len(target), cost) for progress, cost in dp])
print(oc)
print(-minus_cost)


#include <bits/stdc++.h>
using namespace std;

int main() {
string s;
cin >> s;

vector<int> costs;
int cost;
for (int i = 0; i < s.size(); i++) {
cin >> cost;
costs.push_back(cost);
}

string target = "bessie";
vector<pair<int, int>> dp(target.size(), {-1e9, 0});
dp[0] = {0, 0};

for (int i = 0; i < s.size(); i++) {
vector<pair<int, int>> ndp(target.size(), {-1e9, 0});
char c = s[i];
for (int j = 0; j < target.size(); j++) {
ndp[j] =
max(ndp[j], {dp[j].first, dp[j].second - (j > 0) * costs[i]});
if (target[j] == s[i]) {
int k = (j + 1) % target.size();
ndp[k] = max(ndp[k], {dp[j].first + 1, dp[j].second});
}
}
swap(dp, ndp);
}

pair<int, int> mx{-1e9, 0};
for (int i = 0; i < target.size(); i++)
mx = max(mx, {dp[i].first / target.size(), dp[i].second});

cout << mx.first << endl;
cout << -mx.second << endl;

return 0;
}