Subtask 1

For this subtask, the simplest solution is probably, for all indices ~i~, determine, if water was poured here, the endpoints of the interval ~L_i~ and ~R_i~. Now run a dp[i] where dp[i] represents the minimum cost such that the first ~i~ cells have water in them. This should be a fairly classical DP: sort the intervals and transition in ~\mathcal O(N)~. Note that intervals can overlap.

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

Subtask 2

We can extend the previous solution. We need to calculate ~L_i~ more efficiently. Walk through the indices and keep track of the running ~L~ value. When you are on flat ground for too long, you should update this running ~L~ value. Note that our ~R~ values are the same, but done in reverse.

With these intervals, we can do two things. The first is to run a greedy solution where we take the interval with the farthest right point that still covers the leftmost uncovered cell, which works because the intervals are monotonically sorted by both ~L_i~ and ~R_i~. The second is to miss this observation and throw a segment tree on top of our previous DP.

Time Complexity: ~\mathcal O(N)~ or ~\mathcal O(N \log N)~