鍵となる事実は各 \(0\leq i\leq N-1\) について、「\(i\) 回目のコイントスが終わった時点でのカウンタの数値 \(C\) が分かっていれば、 \(i+1\) 回目から \(N\) 回目までのコイントスで得られるお金の最大値は(カウンタの数字が \(C\) となるような出方である限り) \(1\) 回目から \(i\) 回目のコインの表裏の出方によらない」という事にあります。

よって、「\(i\) 回目までコイントスをやって」、「現在のカウンタの数値が\(j\) である」ような条件の下で \(1\) 回目から \(i\) 回目までで得られる金額の最大値を更新していけばよいことが分かります。 この最大値を \(dp[i][j]\) とします。ただし、そのような状況があり得ない、すなわち \(i<j\) であるような 場合は \(dp[i][j]=-\infty\) とします。

まず、初期値、 \(dp[0][j]\) について考えます。 最初カウンタの数字は \(0\) ですから、\(dp[0][0]=0, dp[0][j]=-\infty\) \((j>0)\) となります。

次に、dp 配列の更新について考えます。 \(0\leq i\leq i_0\) について \(dp[i][j]\) が定まっているとき、 \(dp[i_0+1][j]\) の値について考えます。
まず、\(j_0>0\) のときについてです。このようになるのは\(i_0\) 回目のコイントスが終わった時点でカウンタの値が \(j_0-1\) であり、\(i_0+1\) 回目に表が出た場合しかありえません。よって、 \(dp[i_0+1][j_0]=dp[i_0][j_0-1]+X_{i_0+1}+B_{j_0}\) となります。ここで、\(B_{j_0}\) は連続ボーナスであり、\(C_k=j_0\) なる \(k\) が存在するならば \(B_{j_0}=Y_k\), しないならば\(B_{j_0}=0\) です。
次に、\(j_0=0\) となるのは \(i_0+1\)回目に裏が出た場合です。よって、\(dp[i_0+1][0]=\displaystyle\max_j(dp[i_0][j])\) となります。\(i_0<j\)ならば\(dp[i_0][j]=-\infty\) であることに注意すると \(dp[i_0+1][0]=\displaystyle\max_{0\leq j\leq i_0}(dp[i_0][j])\) となります。

答えは \(\displaystyle\max_{0\leq j\leq N}(dp[N][j])\) で求まります。

このとき計算量は、全体で\(O(N^2)\) となり十分高速です。 よって、この問題を解くことができました。

c++による実装例 :

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

int main(void) {
	int n, m;
	long long x[5001];
	long long c, y;
	long long b[5001], dp[5001][5001];
	long long ans;
	for (int i = 0; i <= n; i++)b[i] = 0;

	cin >> n >> m;
	for (int i = 0; i < n; i++)cin >> x[i + 1];
	for (int i = 0; i < m; i++) {
		cin >> c >> y;
		b[c] = y;
	}

	dp[0][0] = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= i; j++) dp[i][j] = dp[i - 1][j - 1] + x[i] + b[j];

		dp[i][0] = 0;
		for (int j = 0; j < i; j++)dp[i][0] = max(dp[i][0], dp[i - 1][j]);
	}

	ans = 0;
	for (int i = 0; i <= n; i++)ans = max(ans, dp[n][i]);
	cout << ans << endl;

	return 0;
}