Let ~dp(l, r)~ be the maximum number of customers we can serve if we still have cakes ~a_l, a_{l+1}, \dots, a_r~ at the table. For the first subtask, we can use the simple transition:

$$\displaystyle dp(l, r) = \max\left(\max_{i=0}^{i<l} (dp(i, r)+check(i, l-1, dp(i, r))), \max_{j=r+1}^{j<n} (dp(l, j)+check(r+1, j, dp(l, j)))\right)$$

where ~check(L, R, x)~ is a function that returns ~1~ if it is possible to satisfy customer ~x~ with the cakes ~a_L, a_{L+1}, \dots, a_R~, and ~0~ otherwise. Time complexity is ~\mathcal O(n^3)~ or ~\mathcal O(n^4)~, depending on the implementation of the function ~check~.

Similarly, for the second subtask if all ~d_i~ are equal to ~1~, then we only need to check ~dp(l-1, r)~ and ~dp(l, r+1)~ to determine ~dp(l, r)~.

That leads us to the complete solution. Is it possible somehow to check only neighbouring states and get the required solution? It is! Instead of memorizing only the maximum number of customers we can serve, we will memorize two more things: the biggest number of cakes that is possible to give to the current customer outside the left and the right border. For example, let ~k~ be the number of cakes we can give to the current customer outside of the left border. Two things need to be satisfied:

• ~dp[l-k][r] = x~ (it is possible to give all the cakes to the current customer)
• ~a_{l-k}, a_{l-k+1}, \dots, a_{l-1} \ge s_x~ (all the cakes have sweetness greater or equal to the required value)

Now we do not need to check every state, only the neighbouring ones. When one of the counters becomes equal to ~d_x~, we can give those cakes to the current customer, and increase the customer number by ~1~. Total time complexity is ~\mathcal O(n^2)~.