Subtask 1

This subtask was intended to reward brute force solutions.

Time Complexity: ~\mathcal{O}(3^N)~

Subtask 2

There are many possible DP solutions to the problem, but we'll only expand on one here.

Let ~dp[i][j]~ be the minimum number of fill operations needed to fill the first ~i~ buckets such that the fill operation was used on bucket ~i~ exactly ~j~ times. For this subtask, we can brute force the transition, resulting in cubic runtime.

Time Complexity: ~\mathcal{O}(N^3)~

Subtask 3

We can optimize the solution from subtask ~2~ with a moving pointer and suffix minimum array.

Alternative Solution

We can do forward DP. Let our state be ~(i, j)~, where the first ~i-1~ buckets are filled and the last bucket has ~j~ units filled. We can either pour ~b_{i-1}~ units into the current bucket, and update the state ~(i, j+b_{i-1})~, or we can fill this bucket with ~a_i~ and move on. In the latter case, let ~r = \left\lceil \frac{c_i-j}{a_i} \right\rceil~. Then we update the state ~(i+1, r \times b_i)~.

Time Complexity: ~\mathcal{O}(N^2)~